Permutations, when arranged in order can be numbered (or indexed or ranked) from 0 to n!-1, where

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.

The number I, which numbers p, can be represented in the factorial number system by a sequence

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 0Permutations, 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

- I is used to get f
- f is used to get f
^{-1} - both f and f
^{-1}are used to get p

Given I, f

f

where [x] = floor(x) = largest integer smaller than or equal to x.

Consider true that I = f

This represents computing the index I from the sequence f.

Now let y such that (substituting for f

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 f

- Obtain f
_{0}= I mod 1 - Do I = [I / 1]
- Obtain f
_{1}= I mod 2 - Do I = [I / 2]
- Obtain f
_{2}= I mod 3 - Do I = [I / 3]
- Obtain f
_{4}= I mod 4 - Do I = [I / 4]
- ...

- Stop when I = 0

It is easy to obtain f

Given f and f

- p
_{level}= level + f^{-1}_{level}- f_{level}

The computation of p can now be generalised to:

- p = {all levels} + f
^{-1}- f

Find the permutation sequence numbered (or ranked or indexed) by I = 2999999 (that is the 3000000

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.

- 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=f
_{level}, 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 f
_{i}< t then increment f^{-1}_{i}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.

initialise the output sequence f^{-1}to 0s. forlevelfrom 0 to n-1: t = f_{level}for i from level-1 down to 0: if f_{i }< t : f^{-1}_{i}+= 1 t -= 1

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(n

The above algorithm obtains f

Let the algorithm be represented as

Let

Let

Let

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^{rev}F. - For any
^{rev}f such that^{rev}f = alg(^{rev}f^{-1}),^{rev}f is an element of F^{-1}. - If f
^{-1}= alg(f) then f = inv_alg(f^{-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:

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 f

For the first iteration involving i=k, f

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.

Let a, such that for a particular level, f

For illustration, consider the sequence {0,1,2,3,3,4,2,4}. At level 6 (7th position), f

The claim is: for any f

Let A and B be the sums of elements of f

The claim is: for any f

An element f of F is a sequence such that f

An element

F contains all possible f sequences, so does

Now for a particular input f to the algorithm, we have:

f

f

......

f

f

So in general, for a particular level:

f

So f

Since

The claim is: for any

A similar approach as that of claim 3 can be used. But there is the need for F

Let the inverse algorithm which obtains f from f

The claim is: if f

... to be updated ...

- http://en.wikipedia.org/wiki/Factorial_number_system
- http://en.wikipedia.org/wiki/Permutation
- http://en.wikipedia.org/wiki/Lehmer_code