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.

---

This page was last updated March 28, 2001.