Rango lexicográfico de una string usando STL

Te dan una string, encuentra su rango entre todas sus permutaciones ordenadas lexicográficamente. 

Ejemplos:

Input : str[] = "acb"
Output : Rank = 2

Input : str[] = "string"
Output : Rank = 598

Input : str[] = "cba"
Output : Rank = 6

Ya hemos discutido soluciones para encontrar el rango lexicográfico de la string . En esta publicación, usamos la función STL «next_permutation()» para generar todas las permutaciones posibles de la string dada y, como nos da permutaciones en orden lexicográfico, pondremos un iterador para encontrar el rango de cada string. Mientras iteramos cuando Nuestra string permutada se vuelve idéntica a la string de entrada original, nos separamos del ciclo y el valor del iterador para la última iteración es nuestro resultado requerido. 

Implementación:

// 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 code
int main()
{
    string str = "GEEKS";
    cout << findRank(str);
    return 0;
}

25

Complejidad de Tiempo: O(n log n)
Espacio Auxiliar: O(1)

Este artículo es una contribución de Aarti_Rathi y Shivam Pradhan (anuj_charm) . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.