Permutaciones de una string dada usando STL

Una permutación, también llamada «número de arreglo» u «orden», es un reordenamiento de los elementos de una lista ordenada S en una correspondencia uno a uno con S mismo. ¡Una string de longitud n tiene n! permutación. 
Fuente: Mathword

A continuación se muestran las permutaciones de la string ABC. 

“ABC”, “ACB”, “BAC”, “BCA”, “CBA”, “CAB” 

Hemos discutido la implementación de C para imprimir todas las permutaciones de una string dada usando el retroceso aquí . En esta publicación, se analiza la implementación de C++ usando STL.

Método 1 (Usando la función std::rotate de rotate()) 
rota los elementos de un vector/string de modo que el elemento central pasado se convierte en el primero. Por ejemplo, si llamamos a rotar para «ABCD» con medio como segundo elemento, la string se convierte en «BCDA» y si llamamos de nuevo a rotar con medio como segundo elemento, la string se convierte en «CDAB». Consulte esto para ver un programa de muestra.
 

A continuación se muestra la implementación de C++. 

// C++ program to print all permutations with
// duplicates allowed using rotate() in STL
#include <bits/stdc++.h>
using namespace std;
 
// Function to print permutations of string str,
// out is used to store permutations one by one
void permute(string str, string out)
{
    // When size of str becomes 0, out has a
    // permutation (length of out is n)
    if (str.size() == 0)
    {
        cout << out << endl;
        return;
    }
 
    // One be one move all characters at
    // the beginning of out (or result)
    for (int i = 0; i < str.size(); i++)
    {
        // Remove first character from str and
        // add it to out
        permute(str.substr(1), out + str[0]);
 
        // Rotate string in a way second character
        // moves to the beginning.
        rotate(str.begin(), str.begin() + 1, str.end());
    }
}
 
// Driver code
int main()
{
    string str = "ABC";
    permute(str, "");
    return 0;
}

ABC
ACB
BCA
BAC
CAB
CBA

Complejidad temporal: O(n*n!) 
Espacio auxiliar : O(n) 

Método 2 (usando next_permutation) 
Podemos usar next_permutation que modifica una string para que almacene lexicográficamente la siguiente permutación. Si la string actual es lexicográficamente más grande, es decir, «CBA», entonces next_permutation devuelve false.

Primero ordenamos la string, de modo que se convierta en la permutación lexicográficamente más pequeña. Luego llamamos uno por uno a next_permutation hasta que devuelve falso.

// C++ program to print all permutations with
// duplicates allowed using next_permutation
#include <bits/stdc++.h>
using namespace std;
 
// Function to print permutations of string str
// using next_permutation
void permute(string str)
{
    // Sort the string in lexicographically
    // ascending order
    sort(str.begin(), str.end());
 
    // Keep printing next permutation while there
    // is next permutation
    do {
       cout << str << endl;
    } while (next_permutation(str.begin(), str.end()));
}
 
// Driver code
int main()
{
    string str = "CBA";
    permute(str);
    return 0;
}

ABC
ACB
BAC
BCA
CAB
CBA

Complejidad temporal: O(n*n!) 
Espacio auxiliar: O(1) 

Tenga en cuenta que el segundo método siempre imprime permutaciones en orden ordenado lexicográficamente, independientemente de la string de entrada.
Este artículo es una contribución de Aarti_Rathi y Aditya Goel . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo y enviarlo 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.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.