Algorithme C++ pour N! commandes

Question

J'ai une liste de N articles et je me demande comment je peux parcourir la liste pour obtenir chaque combinaison. Il n'y a pas de double, donc j'ai besoin de tout N! commandes. La mémoire supplémentaire n'est pas un problème, j'essaie de penser à l'algorithme le plus simple mais j'ai des problèmes.

Answer 1

Voir std::next_permutation    

Answer 2

C++ STL a next_permutation à cet effet.

Answer 3

expansion sur les réponses des autres, voici un exemple de std :: next_permutation adapté 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

algorithme simple en utilisant la récursivité:

pseudocode

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 n'a pas testé, mais devrait fonctionner. Peut-être que ce n'est pas la façon la plus intelligente de le faire, mais c'est un moyen facile. Si quelque chose ne va pas, faites-le moi savoir!

Answer 5

Essayez de construire récursivement l'ensemble des combinaisons avec un nombre fixe d'éléments possibles. L'ensemble de toutes les combinaisons possibles sera l'union des ensembles de combinaisons de 1 élément, 2 éléments, ... jusqu'à N éléments.

Ensuite, vous pouvez attaquer chaque combinaison de taille fixe individuellement.