Algoritmo C++ para N! pedidos

Question

Tengo una lista de N elementos y me pregunto cómo puedo recorrer la lista para obtener todas las combinaciones. No hay dobles, ¡así que necesito obtener todo N! ordenamientos La memoria extra no es un problema, estoy tratando de pensar en el algoritmo más simple pero estoy teniendo problemas.

Answer 1

Ver std::next_permutation    

Answer 2

C++ STL tiene next_permutation para este propósito.

Answer 3

Ampliando las respuestas de otros, aquí está un ejemplo de std :: next_permutation adaptado de cplusplus.com

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

void outputArray(int* array, int size) 
{ 
    for (int i = 0; i < size; ++i) { cout << array[i] << " "; } 
} 

int main() 
{ 
    int myints[] = { 1, 2, 3, 4, 5 }; 
    const int size = sizeof(myints); 

    cout << "The 5! possible permutations with 5 elements:\n"; 

    sort (myints, myints + size); 

    bool hasMorePermutations = true; 
    do 
    { 
    outputArray(myints, size); 
    hasMorePermutations = next_permutation(myints, myints + size); 
    } 
    while (hasMorePermutations); 

    return 0; 
} 

Answer 4

algoritmo simple utilizando recursividad:

Pseudocódigo

getPermutations(CurItemList , CurPermList) 

if CurItemList.isempty() 
    return CurPermList 
else 
    Permutations = {} 

    for i = 1 to CurItemList.size() 
     CurPermList.addLast(CurItemList.get(i)) 

     NextItemList = CurItemList.copy() 
     NextItemList.remove(i) 

     Permutations.add(getPermutations(NextItemList, CurPermList)) 

     CurPermList.removeLast() 


return Permutations 

// To make it look better 
Permutations(ItemList) 
    return getPermutations(ItemList, {}) 

I no lo probé, pero debería funcionar. Tal vez no es la forma más inteligente de hacerlo, pero es una manera fácil. ¡Si algo está mal, por favor avíseme!

Answer 5

Intente crear el conjunto de combinaciones recursivamente con un recuento fijo de posibles elementos. El conjunto de todas las combinaciones posibles será la unión de los conjuntos de combinaciones de 1 elemento, 2 elementos, ... hasta N elementos.

Luego puede atacar cada combinación de tamaño fijo individualmente.