next permutation c++

¿Por qué next_permutation omite algunas permutaciones?

Question

¿Por qué esta simple función no genera todas las permutaciones de la cadena de 5 letras ingresada? Creo que debería haber 120 y solo 90.

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;

// Creates permutation lists for strings
vector<string> createdcombos2(string letters)
{ 
    vector<string> lettercombos;    

    cout << "Letters are: " << letters << endl; //input string

    do 
        lettercombos.push_back(letters);        
    while(next_permutation(letters.begin(), letters.end()));    

    cout <<"Letter combos: " << endl;  //print out permutations 
    for (auto i : lettercombos)
        cout << i << endl;
    cout << endl << lettercombos.size() << endl; //number of permutations

    return lettercombos;
}


int main() 
{
    string letters = "gnary"; 
    vector<string> lettercombos;

    lettercombos = createdcombos2(letters);
}

Answer 1

Como se indica en algunas de las respuestas anteriores, si desea utilizar el valor de retorno bool de std::next_permutation para detener las iteraciones, debe asegurarse de que comienza desde una permutación "ordenada". De lo contrario, su ciclo terminará prematuramente.

Sin embargo, esto no es absolutamente necesario.

Las permutaciones enumeradas a través de std::next_permutation forman una secuencia cíclica sin un principio o un final, lo que significa que puede llamar a std::next_permutation indefinida y recorrerá la misma secuencia de 120 permutaciones una y otra vez. Esto significa que puede comenzar desde cualquier permutación en ese ciclo. Solo tiene que recordar su permutación inicial y observar el momento en que esta permutación aparezca nuevamente. En el mismo momento en que llegas a tu permutación original, la iteración termina. En su caso, se espera que tome 120 llamadas a std::next_permutation .

Por ejemplo, el siguiente código imprime todas las permutaciones de 5 letras para el conjunto "abcde" a pesar de que comienza desde una completamente arbitraria

std::string start = "cadeb", current = start;
do
  std::cout << current << std::endl;
while (std::next_permutation(current.begin(), current.end()), current != start);

Sin embargo, se puede notar que comparar las permutaciones en cada iteración del ciclo es más costoso que usar el valor de retorno de std::next_permutation (que viene "gratis" de las entrañas del algoritmo), así que si está satisfecho con la solución que Pre-ordena la permutación inicial, entonces de hecho es una forma más eficiente de hacerlo.

Alternativamente, si conoce el número exacto de permutaciones en el ciclo (120 en este caso), simplemente puede llamar a std::next_permutation exactamente esa cantidad de veces (como se sugiere en la respuesta de @ Potatoswatter).

Answer 2

El valor bool next_permutation de next_permutation es como una condición de desbordamiento o un bit de acarreo. Es false cuando avanza desde la última permutación a la primera, en orden lexicográfico. Pero sigue avanzando, incondicionalmente.

Si sabe que hay exactamente 120 permutaciones, puede ignorar el valor de retorno y simplemente hacer un bucle ciego:

for ( int i = 0; i != 120; ++ i ) {
    lettercombos.push_back(letters);        
    next_permutation(letters.begin(), letters.end());
}

Answer 3

Para devolver todas las permutaciones en un bucle hasta que next_permutation devuelva falso, el vector debe ordenarse antes del inicio del bucle. next_permutation devuelve las permutaciones en orden ascendente. Entonces, si comienzas con un vector no clasificado, comenzará en parte a través de la serie de permutaciones.

std::sort(letters.begin(), letters.end());
do 
    lettercombos.push_back(letters);        
while(next_permutation(letters.begin(), letters.end()));  

Answer 4

next_permutation ordenar la entrada, next_permutation devolverá la siguiente permutación en orden lexicográfico. Debido a que la permutación de entrada: "gnary" es lexicográficamente "más grande" que una permutación como "enojada" , esas permutaciones "más pequeñas" nunca se alcanzarán.

Puedes ordenar la cadena usando std::sort()