Permutations, when arranged in order can be numbered (or indexed or ranked) from 0 to n!-1, where n is the size of a permutation sequence. Recall that n! = n×(n-1)×...×2×1 and 0!=1.
This article presents a new, very simple and efficient algorithm to generate a particular permutation sequence given its index in the lexicographic order of permutations. The algorithm makes use of the factorial number system and its complement, the Lehmer code.
Let I be the index of (or rank of) a particular permutation. Let p be the permutation sequence of the form {p0, p1, p2, ..., pn-2, pn-1}. plevel in this sequence is an integer between 0 and n-1 inclusive. It is found at a certain level (or position) in the sequence p. So there are n levels from 0 to n-1.
The number I, which numbers p, can be represented in the factorial number system by a sequence f, of the form {f0, f1, f2, ..., fn-2, fn-1}. flevel in this sequence is an integer between 0 and level inclusive. The corresponding Lehmer code sequence f-1 is of the form {f-10, f-11, f-12, ..., f-1n-2, f-1n-1}. f-1level in this sequence is an integer between 0 and n-1-level inclusive.
Below is an example of numbered permutations in order, for the case of n=3.
Permutations, the factorial number system and the Lehmer code have a natural relationship. For a given size n, a permutation of all n! permutations can be described by a corresponding sequence f in the factorial number system, of all the n! possible such sequences, or by a corresponding Lehmer code sequence f-1.
Overall algorithm
The algorithm to generate a particular permutation given its index, I, consists of three steps:
I is used to get f
f is used to get f-1
both f and f-1 are used to get p
1) Get f from I
Given I, flevel is given by:
flevel = [ I / level! ] - [ I / (level+1)! ]*(level+1) = [ ( I mod (level+1)! ) / level! ]
where [x] = floor(x) = largest integer smaller than or equal to x.
Proof:
Consider true that I = f0*0! + f1*1! + f2*2! + ... + fn-2*(n-2)! + fn-1*(n-1)!
This represents computing the index I from the sequence f.
Now let y such that (substituting for flevel in the equation for I above):
y = ([ I / 0!] - [ I / 1!]*1) *0! + ([ I / 1!] - [ I / 2!]*2) *1! + ([ I / 2!] - [ I / 3!]*3) *2! + ... + ([ I / (n-2)! ] - [ I / (n-1)! ]*(n-1)) *(n-2)! + ([ I / (n-1)!] - [ I / n! ]*n) *(n-1)!
Simplifying the expression,
=> y = [ I / 0!]*0! - [ I / 1!]*1! + [ I / 1!]*1! - [ I / 2!]*2! + [ I / 2!]*2! - [ I / 3!]*3! + ... + [ I / (n-2)! ]*(n-2)! - [ I / (n-1)! ]*(n-1)! + [ I / (n-1)! ]*(n-1)! - [ I / n! ]*n!
After massive cancellation, only the first and last terms remain,
=> y = [ I / 0! ]*0! - [ I / n! ]*n!
But I < n!,
=> y = I - 0
=> y = I
Since y=I, it follows thatflevel = [ I / level! ] - [ I / (level+1)! ]*(level+1).
There is a better method that does not involve computing factorials. It follows directly from the equation for I above. Basically, the flevel values are obtained progressively as follows:
Obtain f0 = I mod 1
Do I = [I / 1]
Obtain f1 = I mod 2
Do I = [I / 2]
Obtain f2 = I mod 3
Do I = [I / 3]
Obtain f4 = I mod 4
Do I = [I / 4]
...
Stop when I = 0
Finding all flevel values from f0 to fn-1 forms a total of n operations.
2) Get f-1 from f
It is easy to obtain f-1 given f. The algorithm in the next section does this with n(n-1) operations.
3) Get p from f and f-1
Given f and f-1, plevel in p is given by:
plevel = level + f-1level - flevel
Let {all levels} be the sequence {0, 1, 2, ..., n-2, n-1}.
The computation of p can now be generalised to:
p = {all levels} + f-1 - f
This forms n operations.
Example:
Find the permutation sequence numbered (or ranked or indexed) by I = 2999999 (that is the 3000000th permutation).
Solution:
Using n operations to find f from I,
f = {0, 1, 2, 3, 4, 3, 1, 3, 2, 8}
Using n(n-1) operations to find f-1 from f,
f-1 = {9, 6, 4, 2, 0, 1, 3, 1, 1, 0}
Using n operations to find p,
p = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
+ {9, 6, 4, 2, 0, 1, 3, 1, 1, 0}
- {0, 1, 2, 3, 4, 3, 1, 3, 2, 8}
=> p = {9, 6, 4, 2, 0, 3, 8, 5, 7, 1}
The overall performance is n+n(n-1)+n = n(n+1) operations.
Finding the Lehmer code
The algorithm uses the sequence f of the factorial number system to generate the corresponding Lehmer code sequence f-1. The basic idea is as follows:
Initialise the output sequence f-1 to {0, 0, 0, ... n times}.
Iterate over all the levels of the input sequence f.
For a given level, record the value t=flevel, then iterate over the preceding levels in descending order. That is from i=level-1 down to i=0.
On each iteration of i, if fi < t then increment f-1i and decrement t by 1.
Because t is progressively decremented, t=0 at the end of the iterations of i. Though t may already be 0 at some i>0.
In high-level language, the algorithm is as follows:
initialise the output sequence f-1 to 0s.
for level from 0 to n-1:
t = flevel
for i from level-1 down to 0:
if fi < t :
f-1i += 1
t -= 1
Performance:
Every level contains iterations from i=level-1 down to i=0, each doing constant work. So every level exhibits a 'level' number of operations. The levels run from 0 to n-1. This forms a total of n(n-1) operations. Therefore the performance is O(n2).
The above algorithm obtains f-1 from f. The algorithm to obtain f from f-1 is similar, with the only difference that the iterations of i are over the succeeding levels in ascending order. That is from i=level+1 up to i=n-1.
Proof of the algorithm
Proof of the algorithm to find the Lehmer code sequence presented in the previous section.
Let the algorithm be represented as output = alg(input) .
Let F and F-1 be the set of all n! possible f and f-1 sequences respectively.
Let revf and revf-1 be the sequences obtained from reversing f and f-1 respectively.
Let revF and revF-1 be the set of all n! possible revf and revf-1 sequences respectively.
The following claims will be discussed:
For any level, t=0 at the end of the iterations of i.
For any f-1 such that f-1 = alg(f), the sum of elements of f-1 = the sum of elements of f.
For any f-1 such that f-1 = alg(f), f-1 is an element of revF.
For any revf such that revf = alg(revf-1), revf is an element of F-1.
If f-1 = alg(f) then f = inv_alg(f-1).
Claim 1:
Let the statement P(level) be: for level, t=0 at the end of the iterations of i.
The claim is that P(level) is true for any level. It can be divided into two parts:
Part 1: for any level such that flevel = level, P(level) is true. Proof:
This can be easily proven by mathematical induction.
1- P(0) is true. Here t is initialised to 0 (but there is no iterations of i).
2- Suppose that P(k) is true.
3- P(k+1) has fk+1 = k+1. So t is initialised to t=k+1.
For the first iteration involving i=k, fk <= k < t. t is then decremented to t=k at the end of this iteration.
On the second iteration, i moves down from i=k to i=k-1, while t=k. This gives the situation of P(k).
Therefore if P(k) is true, then P(k+1) is also true.
Since P(0) is true, it follows by induction that P(level) is true.
Part 2: for any level such that flevel < level, P(level) is true. Proof:
Let a, such that for a particular level, flevel = level-a. t is initialised to t=level-a. t can be decremented in some of the iterations of i, not necessarily all. However, the way t gets decremented in the case of P(level) where flevel = level-a, is at worst the way it would get decremented in the case of P(level-a) where flevel-a = level-a. But we proved before that P(level-a), where flevel-a = level-a, is true. So the case of P(level) is at worst the case of P(level-a) and therefore is at worst true.
For illustration, consider the sequence {0,1,2,3,3,4,2,4}. At level 6 (7th position), flevel=2 and a=4. Due to the comparison fi < t, t (from t=flevel=2) will decrease to t=0, at the iterations where i=1 and i=0 only. t will definitely not be greater than 0 at the end of the iterations of i>1, because it will at worst (and just like in this example) behave like the case of level 2 (at 3rd position).
Claim 2:
The claim is: for any f-1 such that f-1 = alg(f), the sum of elements of f-1 = the sum of elements of f. Proof:
Let A and B be the sums of elements of f-1 and f respectively. Initially A=0. t always carries values of flevel for the different levels, and ends up being 0 at the end of the iterations of i. Also, every time t is decremented A is incremented. Therefore as t reduces from flevel to 0, A increases by flevel. A becomes a sum of all flevel values = B.
Claim 3:
The claim is: for any f-1 such that f-1 = alg(f), f-1 is an element of revF. Proof:
An element f of F is a sequence such that flevel <= level for all levels.
An element revf of revF (reversed F) is a sequence such that revflevel <= (n-1-level) for all levels.
F contains all possible f sequences, so does revF.
Now for a particular input f to the algorithm, we have:
f-10 = (1 or 0 from f1) + (1 or 0 from f2) + ... + (1 or 0 from fn-2) + (1 or 0 from fn-1)
f-11 = (1 or 0 from f2) + (1 or 0 from f3) + ... + (1 or 0 from fn-2) + (1 or 0 from fn-1)
......
f-1n-2 = (1 or 0 from fn-1)
f-1n-1 = 0
So in general, for a particular level:
f-1level = sum from (i=level+1) to (i=n-1) of (1 or 0 from fi)
So f-1level <= (n-1-level) for all levels.
Since revF contains all possible revf sequences, f-1 is an element of revF.
Claim 4:
The claim is: for any revf such that revf = alg(revf-1), revf is an element of F-1. Proof:
A similar approach as that of claim 3 can be used. But there is the need for F-1 to indeed contain all n! possible f-1 sequences. This is true if and only if the relationship between F and F-1 is one-to-one.
Claim 5:
Let the inverse algorithm which obtains f from f-1 be represented as output = inv_alg(input).
The claim is: if f-1 = alg(f) then f = inv_alg(f-1). Proof: ... to be updated ...