Find the index of a given permutation in the list of permutations in lexicographic order

Question

Possible Duplicate:
Given a string and permutation of the string. Find the index of this permuted string in the sorted list of the permutations of the string.

This is an interview question. Let there is a list of permutations in lexicographic order. For example, 123, 132, 213, 231, 312, 321. Given a permutation find its index in such a list. For example, the index of permutation 213 is 2 (if we start from 0).

Trivially, we can use a next_permutation algorithm to generate a next permutation in lexicographic order, but it leads to O(N!) solution, which is obviously non-feasible. Is there any better solution?

Answer 1

This solution came into my mind (but I didn't test it yet).

The first digit is from range 1 to N, thus you can derive from the first digit whether your permutation is in which block of size (N-1)!

2*(2!) + X where X = 0..2!-1

Then you can recursively apply this to the next digits (which is one of (N-1)! permutations).

So with an arbitrary N you can do the following algorithm:

X = 0
while string <> ""
  X += ((first digit) - 1) * (N-1)!
  decrease all digits in string by 1 which are > first digit
  remove first digit from string
  N -= 1
return X

In your case:

X = 2
s = "213"
X += (2-1) * 2! => 2
s = "12"
X += (1-1) * 1! => 2
s = "1"
X += (1-1) * 0! => 2

Thus this algorithm is O(N^2).

Answer 2

Multiply the index of the first digit among the digits in the permutation by (n-1)! and add the index of the remaining permutation.

For example, 2 has index 1, and the index of 13 is 0, so the result is 1 * (3-1)! + 0 = 1 * 2 = 2.

Answer 3

• First element in the permutation gives you a subrange of N!
• Remove first element
• Renumber the remaining elements to remove gaps
• Recurse

Answer 4

In C using recursion it will be something like this

int index(char *abc, int size)  
{   
   if(abc ==0 || *abc==0 || size == 0)  
  {  
    return 0;;  
  }  
  return ((abc[0] - '0') * pow(2,size-1)) + index(abc + 1, size -1);   
}