Given a string, calculate its rank among all its 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

Lexicographic rank of the string DCBA is 24

Lexicographic rank of the 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.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 |
#include <iostream> #include <string> using namespace std; // Function to find Lexicographic rank of a string using // std::next_permutation int findLexicographicRank(string key) { string str = key; int rank = 1; // rank starts from 1 // sort the string in ascending order sort(str.begin(), str.end()); while (1) { // if current permutation is equal to the key, return its rank if (key == str) return rank; // find next lexicographically ordered permutation if (!next_permutation(str.begin(), str.end())) break; rank++; } } // Find Lexicographic rank of a string int main() { string key = "DCBA"; cout << "Lexicographic Rank of " << key << " is " << findLexicographicRank(key); return 0; } |

`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(n ^{2})` 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++/Java implementation based on above idea –

## C++

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 |
#include <iostream> #include <string> using namespace std; // Recursive function to calculate factorial of a number int factorial(int n) { return (n <= 2) ? n : n * factorial(n - 1); } // Function to find Lexicographic rank of a string int findLexicographicRank(string str, int n) { // rank starts from 1 int rank = 1; for (int i = 0; i < n; i++) { // count all smaller characters than str[i] to the right of i int count = 0; for (int j = i + 1; j <= n; j++) { if (str[i] > str[j]) count++; } // add current count to the rank rank += count * factorial(n - i); } return rank; } // Find Lexicographic rank of a string int main() { string str = "DCBA"; int n = str.length(); cout << "Lexicographic Rank of " << str << " is " << findLexicographicRank(str, n - 1); return 0; } |

## Java

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 |
class LexicographicRank { // Recursive function to calculate factorial of a number public static int factorial(int n) { return (n <= 2) ? n : n * factorial(n - 1); } // Function to find Lexicographic rank of a string public static int findLexicographicRank(String str, int n) { // rank starts from 1 int rank = 1; for (int i = 0; i < n; i++) { // count all smaller characters than str[i] to the right of i int count = 0; for (int j = i + 1; j <= n; j++) { if (str.charAt(i) > str.charAt(j)) count++; } // add current count to the rank rank += count * factorial(n - i); } return rank; } // main function public static void main(String[] args) { String str = "DCBA"; int n = str.length(); System.out.print("Lexicographic Rank of " +str +" is " + findLexicographicRank(str, n - 1)); } } |

`Output:`

Lexicographic Rank of DCBA is 24

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

**Thanks for reading.**

Please use our online compiler to post code in comments. To contribute, get in touch with us.

Like us? Please spread the word and help us grow. Happy coding 🙂

## Leave a Reply