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

Question

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

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

Trivially, we can use the next_permutation algorithm to generate the next permutation in lexicographical order, but this leads to the solution O (N!), Which is obviously not feasible. Is there a better solution?

Answer 1

This solution occurred to me (but I have not tested it yet).

The first digit is in the range from 1 to N, so you can get from the first digit whether your permutation is in what size block (N-1)!

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

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

So, with 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 index 13 is 0 , so the result is 1 * (3-1)! + 0 = 1 * 2 = 2 1 * (3-1)! + 0 = 1 * 2 = 2 .

Answer 3

• The first element in the permutation gives you the N! subband N!
• Delete first item
• Renumber the remaining items to remove spaces.
• 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);   
 }