Ja, es gibt einen "Next Permutation" -Algorithmus, der auch recht einfach ist. Die C ++ Standard Template Library (STL) hat sogar eine Funktion namensnext_permutation
.
Der Algorithmus findet tatsächlich die nächste Permutation - die lexikographisch nächste. Die Idee ist folgende: Angenommen, Sie erhalten eine Sequenz, sagen Sie "32541". Was ist die nächste Permutation?
Wenn Sie darüber nachdenken, werden Sie sehen, dass es "34125" ist. Und Ihre Gedanken waren wahrscheinlich so: In "32541",
- Es gibt keine Möglichkeit, die "32" festzuhalten und eine spätere Permutation im "541" -Teil zu finden, da diese Permutation bereits die letzte für 5,4 und 1 ist - sie wird in absteigender Reihenfolge sortiert.
- Sie müssen also die "2" in etwas Größeres ändern - tatsächlich in die kleinste Zahl, die größer ist als im "541" -Teil, nämlich 4.
- Sobald Sie entschieden haben, dass die Permutation mit "34" beginnt, sollten die restlichen Zahlen in aufsteigender Reihenfolge angezeigt werden, sodass die Antwort "34125" lautet.
Der Algorithmus soll genau diese Argumentation implementieren:
- Finden Sie den längsten "Schwanz", der in absteigender Reihenfolge bestellt wird. (Der Teil "541".)
- Ändern Sie die Zahl kurz vor dem Schwanz (die "2") in die kleinste Zahl, die größer ist als die im Schwanz (die 4).
- Sortieren Sie den Schwanz in aufsteigender Reihenfolge.
Sie können (1.) effizient ausführen, indem Sie am Ende beginnen und rückwärts gehen, solange das vorherige Element nicht kleiner als das aktuelle Element ist. Sie können (2.) tun, indem Sie einfach die "4" mit der "2" tauschen, so dass Sie "34521" haben. Sobald Sie dies tun, können Sie die Verwendung eines Sortieralgorithmus für (3.) vermeiden, da der Schwanz war und ist (denken Sie darüber nach) in absteigender Reihenfolge sortiert, so dass es nur umgekehrt werden muss.
Der C ++ - Code macht genau das (sehen Sie sich die Quelle /usr/include/c++/4.0.0/bits/stl_algo.h
auf Ihrem System an oder lesen Sie diesen Artikel ). Es sollte einfach sein, es in Ihre Sprache zu übersetzen: [Lesen Sie "BidirectionalIterator" als "Zeiger", wenn Sie mit C ++ - Iteratoren nicht vertraut sind. Der Code wird zurückgegeben, false
wenn keine nächste Permutation vorliegt , dh wir befinden uns bereits in absteigender Reihenfolge.]
template <class BidirectionalIterator>
bool next_permutation(BidirectionalIterator first,
BidirectionalIterator last) {
if (first == last) return false;
BidirectionalIterator i = first;
++i;
if (i == last) return false;
i = last;
--i;
for(;;) {
BidirectionalIterator ii = i--;
if (*i <*ii) {
BidirectionalIterator j = last;
while (!(*i <*--j));
iter_swap(i, j);
reverse(ii, last);
return true;
}
if (i == first) {
reverse(first, last);
return false;
}
}
}
Es mag scheinen, dass es O (n) Zeit pro Permutation dauern kann, aber wenn Sie genauer darüber nachdenken, können Sie beweisen, dass es O (n!) Zeit für alle Permutationen insgesamt braucht, also nur O (1) - konstante Zeit - pro Permutation.
Das Gute ist, dass der Algorithmus auch dann funktioniert, wenn Sie eine Sequenz mit wiederholten Elementen haben: Mit beispielsweise "232254421" würde er den Schwanz als "54421" finden, die "2" und "4" tauschen (also "232454221"). ), kehren Sie den Rest um und geben Sie "232412245" an, was die nächste Permutation ist.
Angenommen, es handelt sich um eine lexikografische Reihenfolge über die permutierten Werte, gibt es zwei allgemeine Ansätze, die Sie verwenden können:
n
th-Permutation, während Sien
von 0 aufwärts zählen.Für diejenigen (wie ich ;-), die kein C ++ als Muttersprachler sprechen, kann Ansatz 1 aus dem folgenden Pseudocode implementiert werden, wobei eine auf Null basierende Indizierung eines Arrays mit dem Index Null auf der "linken Seite" angenommen wird (wobei eine andere Struktur ersetzt wird) , wie eine Liste, wird "als Übung belassen" ;-):
Hier ist ein Beispiel, das mit einer aktuellen Permutation von CADB beginnt:
Denken Sie beim zweiten Ansatz (direkte Berechnung der dritten
n
Permutation) daran, dass esN!
Permutationen vonN
Elementen gibt. Wenn Sie alsoN
Elemente permutieren , müssen die ersten(N-1)!
Permutationen mit dem kleinsten Element beginnen, die nächsten(N-1)!
Permutationen müssen mit dem zweitkleinsten beginnen und so weiter. Dies führt zu folgendem rekursiven Ansatz (wiederum im Pseudocode, Nummerierung der Permutationen und Positionen von 0):So wird zum Beispiel die 13. Permutation von ABCD wie folgt gefunden:
Im Übrigen kann das "Entfernen" von Elementen durch ein paralleles Array von Booleschen Werten dargestellt werden, das angibt, welche Elemente noch verfügbar sind, sodass nicht bei jedem rekursiven Aufruf ein neues Array erstellt werden muss.
Um die Permutationen von ABCD zu durchlaufen, zählen Sie einfach von 0 bis 23 (4! -1) und berechnen Sie die entsprechende Permutation direkt.
quelle
Sie sollten den Permutations-Artikel über Wikipeda lesen. Es gibt auch das Konzept der faktoradischen Zahlen.
Wie auch immer, das mathematische Problem ist ziemlich schwer.
In können
C#
Sie ein verwendeniterator
und den Permutationsalgorithmus mit stoppenyield
. Das Problem dabei ist, dass Sie nicht hin und her gehen oder eine verwenden könnenindex
.quelle
Weitere Beispiele für Permutationsalgorithmen, um sie zu generieren.
Quelle: http://www.ddj.com/architect/201200326
1.
2.
3.
quelle
Die Permutationsfunktion in clojure.contrib.lazy_seqs behauptet bereits, genau dies zu tun.
quelle