Generating permutations




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.

Contents:

  1. Numbered permutations
  2. Overall algorithm
  3. Finding the Lehmer code
  4. Proof of the algorithm
  5. Links

Numbered permutations

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.
 index(I)   permutation(p)
    0     -    0 1 2
    1     -    1 0 2
    2     -    0 2 1
    3     -    2 0 1
    4     -    1 2 0
    5     -    2 1 0
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:
  1. I is used to get f
  2. f is used to get f-1
  3. 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 that flevel  =  [ 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:
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:
Let {all levels} be the sequence {0, 1, 2, ..., n-2, n-1}.
The computation of p can now be generalised to:
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:
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:

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 ...



Links

  1. http://en.wikipedia.org/wiki/Factorial_number_system

  2. http://en.wikipedia.org/wiki/Permutation

  3. http://en.wikipedia.org/wiki/Lehmer_code