Ranking and Unranking Permutations
This script ranks and unranks a permutation of n distinct integers from the interval [0 .. n-1] (n<10).
The script doesn't check the validity of your input, so it's up to you to take care of it. The algorithm bases on the concept of the Combinatorial Number System[see addendum]. Every permutation can be represented by an assignement matrix which can be represented by a combi-number[see addendum]. For instance the permutation 31420 is represented by the assignement matrix
o o o o x
o x o o o
o o o x o
x o o o o
o o x o o
which is represented by the combi-number[see addendum] k31210=3·4!+1·3!+2·2!+1·1!+0·0!=83.
The ranking and unranking is computed using O(n) 'arithmetic operations', so it does the same
as the algorithm of Myrvold and Ruskey 'Ranking and Unranking Permutations in Linear Time' at http://www.csr.uvic.ca/~fruskey/Publications/RankPerm.html. While the formulation O(n) 'arithmetic operations' is correct, the formulation 'in Linear Time'
seems to be not correct, because the time for an 'arithmetic operation' (Myrvold and Ruskey use multiplication, modulo and integer division) depends on the magnitude of n! (calculation with integer values would be faster than with longinteger values). I think the algorithm used in this script is not as sophisticated as the above mentioned and also the ordering is
a bit nicer then that of the above mentioned algorithm:
(c) Lutz Tautenhahn 1998, 2001
Addendum:
I wrote this page originally in 2001 as a response to a question in the group sci.op-research
Selecting the Rth Permutation for N! pemutations
https://groups.google.com/forum/#!msg/sci.op-research/b0fCiXk4RtA/_kHtreop_F0J
A few years later I noticed that the number system for which I had originally coined the term "Combinatorial Number System" was already described earlier in literature and was named "Factorial Number System" and the term "Combinatorial Number System" was already used for another (similar) number system.
At the time I wasn't aware of this, because it happened that I came up with the idea for the number system independently in 1998/1999 and thought the name "Combinatorial Number System" would fit quite well (described here http://www.lutanho.net/plt/lgrthm/enumera.html).
This was before anything about the "Factorial Number System" could be found on the internet and I also had not known about it from standard math books before.
Since 2004 there exist Wikipedia articles about the "Factorial Number System" https://en.wikipedia.org/wiki/Factorial_number_system
and also the "Combinatorial Number System" https://en.wikipedia.org/wiki/Combinatorial_number_system
So to adapt to the standard naming convention just replace in my original text above from 2001 the term "Combinatorial Number System" with "Factorial Number System" and "combi-number" with "factorial number" then everything is fine.