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,...,i[n-1] be the indices of a permutation and let d,...,d[n-1] be the corresponding segment start numbers. In our example i,...,i[n-1] = (3,4,0,2,1) has d,...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 loopConversely, given a list of segment start numbers, d, we can reconstruct the permutation indices withcopy(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 loopConverting segment start numbers to lexicographic index
The position of a given permutation in the lexicographic list is given by the formula
index = d*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)...)
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 loopIn 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 pseudocodebegin 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 functionExecution 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.