Permutación lexicográficamente siguiente en C++

Todas las permutaciones de una palabra cuando se ordenan en un diccionario, el orden de las palabras así obtenido se llama orden lexicográfico. en palabras simples, es el que tiene todos sus elementos ordenados en orden ascendente, y el más grande tiene todos sus elementos ordenados en orden descendente.

lexicográficamente no es más que la mayor permutación de la misma. 

Para referencia : abcdefghijklmnopqrstu vwxyz

Por ejemplo , lexicográficamente, la siguiente permutación de «gfg» es «ggf» y la siguiente permutación de «acb» es «bac». 
Nota: En algunos casos, la siguiente palabra mayor lexicográficamente podría no existir, por ejemplo, «aaa» y «edcba». 

En C++, hay una función específica que nos ahorra mucho código. Está en el archivo #include <algoritmo>. La función es next_permutation (a.begin(), a.end()) . 
Devuelve ‘verdadero’ si la función puede reorganizar el objeto como una permutación lexicográficamente mayor. De lo contrario, la función devuelve ‘falso’.

Ejemplo:

// C++ program to demonstrate next lexicographically
// greater permutation of a word
 
#include <algorithm>
#include <iostream>
 
using namespace std;
 
int main()
{
    string s = { "gfg" };
    bool val
        = next_permutation(s.begin(),
                        s.end());
    if (val == false)
        cout << "No Word Possible"
            << endl;
    else
        cout << s << endl;
    return 0;
}

ggf

El mismo programa también se puede implementar sin utilizar STL . A continuación se muestra el fragmento de código para el mismo. 

La idea se basa en los siguientes hechos: 

1. Una secuencia ordenada en orden descendente no tiene la siguiente permutación. Por ejemplo, «edcba» no tiene la siguiente permutación.
2. Para una secuencia que no está ordenada en orden descendente, por ejemplo, «abedc», podemos seguir estos pasos.  
   • a) Recorra desde la derecha y encuentre el primer elemento que no sigue el orden ascendente. Por ejemplo en “abedc”, el carácter ‘b’ no sigue el orden ascendente.
   • b) Intercambiar el carácter encontrado con el elemento mayor más cercano (o mayor más pequeño) en el lado derecho del mismo. En el caso de “abedc”, tenemos ‘c’ como elemento mayor más cercano. Después de intercambiar ‘b’ y ‘c’, la string se convierte en «acedb».
   • c) Después del intercambio, invierta la string después de la posición del carácter encontrado en el paso a . Después de invertir la substring «edb» de «acedb», obtenemos » acbde «, que es la siguiente permutación requerida. 

Optimizaciones en los pasos b) yc) 
a) Dado que la secuencia se ordena en orden decreciente, podemos usar la búsqueda binaria para encontrar el elemento mayor más cercano. 

c) Dado que la secuencia ya está ordenada en orden decreciente (incluso después de intercambiar como intercambiamos con el mayor más cercano), podemos ordenar la secuencia (en orden creciente) después de invertirla. 

// C++ program to demonstrate
// the next lexicographically
// greater permutation of a word
#include <iostream>
 
using namespace std;
 
void swap(char* a, char* b)
{
    if (*a == *b)
        return;
    *a ^= *b;
    *b ^= *a;
    *a ^= *b;
}
void rev(string& s, int l, int r)
{
    while (l < r)
        swap(&s[l++], &s[r--]);
}
 
int bsearch(string& s, int l, int r, int key)
{
    int index = -1;
    while (l <= r) {
        int mid = l + (r - l) / 2;
        if (s[mid] <= key)
            r = mid - 1;
        else {
            l = mid + 1;
            if (index == -1 || s[index] >= s[mid])
                index = mid;
        }
    }
    return index;
}
 
bool nextpermutation(string& s)
{
    int len = s.length(), i = len - 2;
    while (i >= 0 && s[i] >= s[i + 1])
        --i;
    if (i < 0)
        return false;
    else {
        int index = bsearch(s, i + 1, len - 1, s[i]);
        swap(&s[i], &s[index]);
        rev(s, i + 1, len - 1);
        return true;
    }
}
 
// Driver code
int main()
{
    string s = { "gfg" };
    bool val = nextpermutation(s);
    if (val == false)
        cout << "No Word Possible" << endl;
    else
        cout << s << endl;
    return 0;
}

ggf

Complejidad del tiempo:

1. En el peor de los casos, el primer paso de next_permutation toma O(n) tiempo.
2. La búsqueda binaria toma un tiempo O(log n) .
3. Lo contrario toma tiempo O(n) .

La complejidad temporal total es O(n). Donde n es la longitud de la string. 
El espacio auxiliar es O(1) , porque no se usa espacio extra.

Este artículo es una contribución de Harshit Gupta . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo en write.geeksforgeeks.org . Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks. Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.