Converting permutations to indices and vice versa

Statement of problem:

Given a permutation P of n elements determine its index I in a lexicographic listing of all permutations. Conversely, given an index I determine the corresponding permutation P.

Here the lexicographic listing refers to the subscripts of the elements. Thus if we have five elements a0,a1,a2,a3,a4 the permutation (a3,a4,a0,a2,a1) would be represented by (3,4,0,2,1). It would be preceded by (3,4,0,1,2) and followed by (3,4,1,0,2).

Decomposition of the lexicographic list into segments:

The lexicographic list can be divided into segments, each one starting with a different index. Each segment can be divided into subsegments and so on. Thus the permuation (3,4,0,2,1) falls into the 3rd segment. The 3rd subsegment has 4 subsegments that start with with 0,1,2,4 respectively. The 3rd sub-subsgement (starting with 4) has 3 subsegments starting with 0,1,2 respectively. The subsegment of that subsegment starting with 0 has two subsegments that start with 1 and 2 respectively. Finally the last subsegment has a single element, 1. To summarize:

 level choices value position in subsequence 0 0,1,2,3,4 3 3 1 0,1,2,4 4 3 2 0,1,2 0 0 3 1,2 2 1 4 1 1 0

Let i[0],...,i[n-1] be the indices of a permutation and let d[0],...,d[n-1] be the corresponding segment start numbers. In our example i[0],...,i[n-1] = (3,4,0,2,1) has d[0],...d[n-1] = (3,3,0,1,0).

In the transition from one level to the next we remove the value for the current list of choices. This has the effect of reducing by 1 all segment start numbers greater than the selection. This gives a simple procedure for determining segment start numbers from the permutation indices.

```        copy(src=perm,dest=d)
begin loop i = 0,...,n-2
begin loop j =i+1,...,n-1
if (d[j] .gt. d[i]) d[j] -= 1
end loop
end loop
```
Conversely, given a list of segment start numbers, d, we can reconstruct the permutation indices with
```        copy(src=d,dest=perm)
begin loop i = 0,...,n-2
begin loop j = i+1,....,n-1
if (perm[j] .ge. perm[i]) perm[j] += 1
end loop
end loop
```
Converting segment start numbers to lexicographic index

The position of a given permutation in the lexicographic list is given by the formula

index = d[0]*factorial(n-1) + ... + d[n-1]*factorial(0)

The computation of factorials can be avoided by using the standard technique for computing polynomials, i.e.,

index = d[n-1]*0! + 1*(d[n-2] + 2*(d[n-3] +...+(n-1)*d[0])...)

which gives us the following for computing the index (noting that d[n-1] is necessarily 0):

```        begin loop i = 0,...,n-2; init index = 0; init j = n-1
index = j*(index + d[i])
j -= 1
end loop
```
In turn the segment start numbers can be determined with the following:
```        d[n-1] = 0
begin loop i = 2,...,n-2; init j = n-2
d[j] = modulo(index,i)
index /= i
j -= 1
end loop
```

Summary of pseudocode

```        begin interface function perm2index(perm,n)
dcl perm int[n]
dcl n    int
return   int
end interface

begin interface fuction index2perm(index,n)
dcl index int
dcl n     int
return    int[n]
end interface

begin function perm2index
dcl i,j   int
dcl d     int[]
dcl index int

copy(src=perm,dest=d)
begin loop i = 0,...,n-2
begin loop j =i+1,...,n-1
if (d[j] .gt. d[i]) d[j] -= 1
end loop
end loop

begin loop i = 0,...,n-2; init index = 0; init j = n-1
index = j*(index + d[i])
j -= 1
end loop

return index
end function

begin function index2perm
dcl i,j   int
dcl d     int[n]
dcl perm  int[n]

d[n-1] = 0
begin loop i = 2,...,n-2; init j = n-2
d[j] = modulo(index,i)
index /= i
j -= 1
end loop

copy(src=d,dest=perm)
begin loop i = 0,...,n-2
begin loop j = i+1,....,n-1
if (perm[j] .ge. perm[i]) perm[j] += 1
end loop
end loop

return perm
end function
```
Execution costs

The code to map the permutation into the segment numbers and vice versa is O(n**2) as given. It can be reduced to O(n*log(n)) by using a binary tree; however the code required is tricky and the gain in performance is likely to be illusory. The code to map segment number to/from lexicographic index is O(n); however the cost per loop cycle will be relatively high because of the arithmetic operations.