You are given a string, find its rank among all its permutations sorted lexicographically.
Examples:
Input : str[] = "acb"
Output : Rank = 2
Input : str[] = "string"
Output : Rank = 598
Input : str[] = "cba"
Output : Rank = 6
We have already discussed solutions to find Lexicographic rank of string In this post, we use the STL function “next_permutation ()” to generate all possible permutations of the given string and, as it gives us permutations in lexicographic order, we will put an iterator to find the rank of each string. While iterating when Our permuted string becomes identical to the original input string, we break from the loop and the iterator value for the last iteration is our required result.
Implementation:
C++
// C++ program to print rank of// string using next_permute()#include <bits/stdc++.h>using namespace std;// Function to print rank of string// using next_permute()int findRank(string str){ // store original string string orgStr = str; // Sort the string in lexicographically // ascending order sort(str.begin(), str.end()); // Keep iterating until // we reach equality condition long int i = 1; do { // check for nth iteration if (str == orgStr) break; i++; } while (next_permutation(str.begin(), str.end())); // return iterator value return i;}// Driver codeint main(){ string str = "cba"; cout << findRank(str); return 0;} |
Python3
# Python program to print rank of# string using itertools.permutationsimport itertools# Function to print rank of string# using itertools.permutationsdef findRank(str): # Store original string and # Sort the string in lexicographically # ascending order orgStr = ''.join(sorted(str)) # Create an dictionary to handle # repeating characters in Python # while using itertools.permutations d=[] # Keep iterating until we reach equality condition i = 1 for permutation in itertools.permutations(orgStr): if permutation not in d: d.append(permutation) # check for nth iteration if ''.join(permutation) == str: break i += 1 # Return iterator value return i# Driver codeif __name__ == '__main__': str = 'bca' print(findRank(str)) # This code is contributed by Utkarsh. |
C#
using System;using System.Collections.Generic;using System.Linq;class Program{ // Function to print rank of string // using itertools.permutations static int FindRank(string str) { // Store original string and // Sort the string in lexicographically // ascending order string orgStr = new string(str.OrderBy(c => c).ToArray()); // Create a set to handle // repeating characters in C# // while using itertools.permutations HashSet<string> set = new HashSet<string>(); // Keep iterating until we reach equality condition int i = 1; foreach (var permutation in Permutations(orgStr)) { if (!set.Contains(permutation)) { set.Add(permutation); // check for nth iteration if (permutation == str) { break; } i++; } } // Return iterator value return i; } // Function to get all permutations of a string static IEnumerable<string> Permutations(string str) { if (str.Length == 1) { yield return str; } else { foreach (var ch in str) { foreach (var permutation in Permutations(str.Remove(str.IndexOf(ch), 1))) { yield return ch + permutation; } } } } // Driver code static void Main(string[] args) { string str = "bca"; Console.WriteLine(FindRank(str)); }}// This code is contributed by shiv1o43g |
Javascript
function findRank(str) { const MOD = 1000003; const n = str.length; let rank = 1; let factorial = 1; for (let i = 0; i < n; i++) { let smaller = 0; for (let j = i + 1; j < n; j++) { if (str[j] < str[i]) { smaller++; } } rank = (rank + (smaller * factorial)) % MOD; factorial = (factorial * (n - i)) % MOD; } return rank;}// Driver codeconst str = "cba";console.log(findRank(str)); |
6
Time Complexity: O(n log n)
Auxiliary Space: O(1)
This article is contributed by Aarti_Rathi and Shivam Pradhan (anuj_charm). If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
