Ich weiß, dass ich std::next_permutation für einen Container verwenden kann, der die Elemente [1, 2, 3] enthält, die 6 Permutationen dieser Sequenz erzeugen würden. Was ich tun möchte, ist ein set [1, 2, 3, 4, 5, 6] erzeugt alle möglichen Permutationen der Größe 3. Also für dieses Beispiel wäre [4, 3, 2] eine der Permutationen, die sich aus diesem Kriterium ergeben. Ich suche nach einer STL-Methode (wenn möglich), anstatt meine eigene Kombinationsfunktion zu schreiben. Irgendeine bestimmte STL-Implementierung, über die ich lesen sollte?
Derzeit gibt es (ab 2016) keine einzige STD-Funktion dafür. Am nächsten kommt der Vorschlag von Ссылка
Die gewünschte Funktion heißt next_partial_permutation und sieht wie folgt aus (ab N2639):
Dies ist nicht der effizienteste mögliche Algorithmus, aber es ist einfach. Sie müssen mit den sortierten Elementen beginnen. Um die nächste k-Permutation zu erhalten, kehren Sie die letzten n-k Elemente um und versuchen Sie dann, die nächste Permutation zu erhalten. Die ersten k Elemente sind die nächste k-Permutation.
Hier ist ein in Smalltalk geschriebener Algorithmus.
Die Idee des Algorithmus besteht darin, die lexikographische Ordnung von Arrays der Länge m mit Elementen zwischen 1 und n zu berücksichtigen. Bei einem solchen array ersetzt die Methode next array durch ihre nächste partielle Permutation in dieser Reihenfolge.
Ich habe eine Klasse mit drei Instanzvariablen erstellt
%Vor% Die Instanzerstellungsmethode m:n: funktioniert wie folgt
In dieser Klasse ändert die Methode next die array so, dass sie jetzt die nächste Permutation enthält.
Es ist vielleicht erwähnenswert, dass der Algorithmus nicht rekursiv ist.
Die Methode next antwortet mit nil iff array enthält die letzte Permutation in der Reihenfolge (d. h. array = (n, n-1, ...., n-m+1) .
Um alle Permutationen zu berechnen, beginnen Sie mit array = (1 ... m) und senden Sie next , bis die Antwort nil ist.
Wo
%Vor%Tags und Links algorithm c++ stl permutation combinations