Calculate Rank of a String among all its Lexicographically Sorted Permutations

Given a string, calculate its rank among all its lexicographically sorted permutations.

 

For example, consider below lexicographically sorted permutations –

ABCD ABDC ACBD ACDB ADBC ADCB BACD BADC BCAD BCDA BDAC BDCA
CABD CADB CBAD CBDA CDAB CDBA DABC DACB DBAC DBCA DCAB DCBA

 

Lexicographically rank of string DCBA is 24
Lexicographically rank of string BDAC is 11

 


 

A simple solution would to use std::next_permutation that generates the next greater lexicographic permutation of a string. The idea is to sort the string in ascending order and calculate repeatedly calculate lexicographic next permutation till current permutation becomes equal to the given string.

 
C++ implementation –
 

Download   Run Code

Output:

Lexicographic Rank of DCBA is 24

 
Note that we can also use std::prev_permutation in place of std::next_permutation that generates the next smaller lexicographic permutation of a string. The implementation can be seen here.

 
The time complexity of above solution is O(n.n!) and auxiliary space used by the program is O(1).

 


 

We can improve worst case time complexity to O(n2) by finding the number of characters are ranked before the current character in the string. Let c[i] denotes count of smaller characters than str[i] to the right of index i. Then, for the string of length n

  • There will be c[0]*(n-1)! permutations ranked above first character in the string.
  • There will be c[1]*(n-2)! permutations ranked above second character in the string.
  • There will be c[2]*(n-3)! permutations ranked above third character in the string and so on..

 
Below is C++ implementation based on above idea –
 

Download   Run Code

Output:

Lexicographic Rank of DCBA is 24

 

The time complexity of above solution is O(n2) and auxiliary space used by the program is O(1).

 
Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 





Leave a Reply

Notify of
avatar
wpDiscuz