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

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 –**

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 |
#include <bits/stdc++.h> 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++ implementation based on above idea –

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 |
#include <bits/stdc++.h> 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; } |

`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 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