Algoritmo C++ per N! ordini

Question

Ho una lista di N elementi e mi chiedo come posso scorrere l'elenco per ottenere ogni combinazione. Non ci sono i doppi, quindi ho bisogno di prendere tutto N! ordinamenti. La memoria extra non è un problema, sto cercando di pensare all'algoritmo più semplice ma ho dei problemi.

Answer 1

Vedi std::next_permutation    

Answer 2

C++ STL ha next_permutation per questo scopo.

Answer 3

Ampliando le risposte degli altri, ecco un esempio di std :: next_permutation adattato da 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

semplice algoritmo utilizzando la ricorsione:

pseudocodice

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 non l'ho provato, ma dovrebbe funzionare Forse non è il modo più intelligente per farlo, ma è un modo semplice. Se qualcosa non va, per favore fatemelo sapere!

Answer 5

Provare a creare il set di combinazioni in modo ricorsivo con un numero fisso di elementi possibili. L'insieme di tutte le combinazioni possibili sarà l'unione delle serie di combinazioni di 1 elemento, 2 elementi, ... fino a N elementi.

Quindi è possibile attaccare ogni combinazione di dimensioni fisse singolarmente.