Je sais que je peux utiliser std :: Next_permutation sur certains conteneurs contenant les éléments [1, 2, 3] qui générerait 6 permutations de cette séquence. Ce que je voudrais faire, il est donné un certain jeu [1, 2, 3, 4, 5, 6] générer toutes les permutations possibles de la taille 3. Donc, pour cet exemple, [4, 3 , 2] serait l'une des permutations résultant de ces critères. Je cherche une manière stl de faire cela (si possible) plutôt que d'écrire ma propre fonction de combinaisons. Toute mise en œuvre de STL particulière que je devrais lire?
3 Réponses :
Ce n'est pas l'algorithme le plus efficace possible, mais c'est facile. Vous devez commencer par les éléments triés. Pour obtenir la prochaine permutation K, inverser les derniers éléments N-K, puis essayer d'obtenir la prochaine permutation. Les premiers k éléments sont la prochaine permutation K.
Semble évident maintenant que vous le dites, +1.
Il y a actuellement (à partir de 2016) Aucun fonctionnement STD unique pour le faire. Le plus proche que vous avez est la proposition de http: / /wwww.open-std.org/jtc1/sc22/wg21/docs/papers/2008/n2639.pdf
La fonction que vous souhaitez s'appelle Next_Partial_permutation code> et ressemble à (de N2639): P> template <class BidirectionalIterator >
bool next_partial_permutation(
BidirectionalIterator first ,
BidirectionalIterator middle ,
BidirectionalIterator last)
{
std::reverse(middle , last);
return std::next_permutation(first , last);
}
Voici un algorithme écrit dans Smalltalk.
L'idée de l'algorithme est de considérer l'ordre lexicographique des matrices de longueur J'ai créé une classe avec trois variables d'instance méthode de création d'instance dans cette classe, la méthode Ça vaut la peine d'être mentionné que l'algorithme n'est pas récursif. la méthode pour calculer toutes les permutations commencez par m avec des éléments entre 1 et < code> n . Compte tenu de ce type tableau , la méthode suivante remplace le tableau avec sa prochaine permutation partielle dans ledit ordre. m: n: fonctionne comme suit suivante modifie le tableau de sorte qu'il tiendra la permutation suivante. suivant répond avec nil iff matrice contient la dernière permutation dans la commande (c.-à-d., array = (n, n-1, ...., n-m + 1) . Array = ( 1 ... m) et envoyer suivant jusqu'à ce que la réponse soit nil .
Stackoverflow.com/Questtions/127704/...
Stackoverflow.com/questions/9430568/...
Stackoverflow.com/Questtions/12991758/...
@Alanstokes: toutes ces questions concernent des combinaisons; Cette question concerne les permutations.
Il s'agit de permuter des combinaisons. Et l'OP sait comment perperger, ce qui vient de trouver les combinaisons. Par conséquent, "je cherche une manière stl de faire cela [...] plutôt que d'écrire ma propre fonction de combinaisons".