Gibt es einen Algorithmus, um alle möglichen Permutationen einer Reihe von einzigartigen Elementen zu finden, die dieser Regel folgen?
Aus einer gegebenen Permutation muss die nächste Permutation gefunden werden, indem genau drei Elemente durchlaufen werden. Sie können drei beliebige Elemente sein.
Mit solchen 3-Zyklen wird nur eine Teilmenge aller Permutationen gefunden, aber alle diejenigen, die über 3-Zyklen erreichbar sind, sollten gefunden werden, und die gleiche Permutation sollte nicht zweimal gefunden werden, bis alle erreichbaren Permutationen gefunden wurden.
Hier ist eine Beispieleingabe:
%Vor%Ausgabe könnte sein:
%Vor%... usw.
Einer der vielen Algorithmen, die ich versucht habe, eine solche Sequenz zu erzeugen, ist die folgende (für Array a und Länge n ):
%Vor%Dies erzeugt die oben aufgedruckte Serie, fährt dann aber mit:
fort %Vor%.. was eine Permutation ist, die bereits ausgegeben wurde. Jeder andere Algorithmus, der den nächsten 3-Zyklus, den ich bisher versucht habe, findet, konnte nicht alle erreichbaren Permutationen finden.
Es gibt dieses alte Papier V. L. Kompel'makher und V. A. Liskovets. Sequenzielle Generierung von Arrangements auf der Basis von Transpositionen. , die zeigt, dass man alle Permutationen durch einfache Transpositionen erzeugen kann und jede dieser Transpositionen das erste Element der Permutation durch irgendein anderes (so genanntes sternförmiges) vertauschen muss Basis). Zum Beispiel für S (3), das wäre, wenn das erste Element (im Gegensatz zu Element 1) in jedem Schritt getauscht wird.
%Vor%Es gibt auch einen ähnlichen Ansatz Ein 'Hot Potato' Gray-Code für Permutationen was nicht hinter einer Lohnmauer ist. Eine wichtige Erkenntnis dieser Arbeit ist, dass selbst wenn in jeder Transposition das Element 1 ausgetauscht werden muss, immer noch alle Permutationen ohne Wiederholung erzeugt werden können (Element 1 wird in jedem Schritt getauscht):
%Vor%Ein weiterer Algorithmus zum Durchlaufen aller Permutationen für die sternförmige Basis ist dieser von Knuths "Die Kunst der Computerprogrammierung", Kapitel "Generieren aller Permutationen". Algorithmus heißt "Ehrlichs Swap-Methode". Ich behaupte nicht zu verstehen, was dort vor sich geht, es ist nur eine Übersetzung des Algorithmus in Java. Der interessanteste Teil für dich ist diese Zeile hier:
%Vor%In jedem Schritt gibt es eine Transposition und in jeder Transposition wird das Element [0] vertauscht (- & gt; sternförmige Basis).
%Vor%Jetzt ist das harte Zeug fertig!
Der letzte Schritt ist: Zwei aufeinanderfolgende Transpositionen der Form (1 a) (1 b) können als 3-Elemente-Zyklus (1 a b) geschrieben werden. Sie würden also einfach mit negativer Parität über die Permutation springen. Für Hot-Potato sieht das so aus:
%Vor%mit Permutationen in () übersprungen.
In meiner vorherigen Antwort auf diese Frage habe ich eine Methode beschrieben, um Sequenzen von gleichgerichteten 3-Element-Rotationen zu finden, die alle (erreichbaren) Permutationen von N Elementen erzeugen. Die einfachste Sequenz, die ich mit dieser Methode finden konnte, wird in der folgenden Implementierung verwendet. Die Rotationen für jede Anzahl von Elementen zeigen ein wiederkehrendes Muster, das sich nur für ungerade / gerade Werte von N unterscheidet; Dies bedeutet, dass die Reihenfolge der Rotationen leicht für eine beliebige Anzahl von Elementen erzeugt werden kann.
%Vor%Ausgehend von 5 Elementen finden Sie dieses wiederkehrende Muster:
%Vor% Oder grafisch, wobei < die Position der gedrehten Elemente angibt:
Das Erzeugen der Permutationen erfolgt dann durch Durchlaufen der Folgen von Drehungen in dieser Reihenfolge, wobei jedes n-te
3,3,4,3,3,4,3,3,4,3,3, <5>, 3,3,4,3,3,4,3,3, 4,3,3, 5,3,3,4,3,3,4,3,3,4,3,3, 5,3,3, 4,3,3,4,3,3,4,3,3, 5,3,3,4,3,3,4,3,3,4,3,3, < b> 6 , ...
so dass die Rotationen sind:
(0,1,2), (0,1,2), (0,1,3), (0,1,2), (0,1,2), (1,2,3) , (0,1,2), (0,1,2), (1,2,3), (0,1,2), (0,1,2), (0,3,4) ) ,
(0,1,2), (0,1,2), (0,1,3), (0,1,2), (0,1,2), (1,2,3), (0 , 1,2), (0,1,2), (1,2,3), (0,1,2), (0,1,2), (0,3,4) ,
(0,1,2), (0,1,2), (0,1,3), (0,1,2), (0,1,2), (1,2,3), (0 , 1,2), (0,1,2), (1,2,3), (0,1,2), (0,1,2), (0,3,4) ,
(0,1,2), (0,1,2), (0,1,3), (0,1,2), (0,1,2), (1,2,3), (0 , 1,2), (0,1,2), (1,2,3), (0,1,2), (0,1,2), (0,3,4) ,
(0,1,2), (0,1,2), (0,1,3), (0,1,2), (0,1,2), (1,2,3), (0 , 1,2), (0,1,2), (1,2,3), (0,1,2), (0,1,2), (0,1,5) , ...
Das folgende Codebeispiel generiert die Rotationssequenzen bis zur angeforderten Anzahl von Elementen und führt dann die Rotationen durch und gibt die resultierenden Permutationen aus.
Hinweis: Ersetzen Sie while (step[seq] == seq - 1) durch while (seq <= elems && step[seq] == seq - 1) in strengeren Sprachen, um Array-Out-of-Bounds-Fehler zu vermeiden.
Um alle Permutationen zu generieren, und nicht nur die Hälfte, die durch 3-Element-Rotation erreicht werden kann, geben Sie jede Permutation zweimal aus, einmal wie sie ist und einmal mit den ersten beiden Elementen.
Ich bin mir ziemlich sicher, dass ich diese Frage nicht bekommen habe, da es sich anhört, als hättest du bereits alle Teile, die du brauchst, um es zu implementieren, aber hier geht es. Bitte hinterlassen Sie einen Kommentar, ob das korrekt klingt oder nicht.
Ich ging für einen rekursiven Ansatz. Zyklus jede Kombination von 3 Elementen, dann rekursiv mit der neuen Kombination. Behandle nur einzigartige Kombinationen.
Hier ist der Code, der als C # -Programm in LINQPad implementiert wurde:
%Vor%Die Ausgabe:
12345, 23145, 31245, 14235, 42135, 21435, 13425, 34125, 41325, 15324, 53124, 31524, 12534, 25134, 51234, 13254, 32154, 21354, 14352, 43152, 31452, 15432, 54132, 41532 13542, 35142, 51342, 45312, 53412, 34512, 42513, 25413, 54213, 41253, 12453, 24153, 45123, 51423, 14523, 43521, 35421, 54321, 42351, 23451, 34251, 45231, 52431, 24531, 32541 25341, 53241, 43215, 32415, 24315, 52314, 23514, 35214, 15243, 52143, 21543
Um Permutationen von N Elementen durch wiederholtes Drehen von 3 Elementen in die gleiche Richtung zu erzeugen, können Sie eine 4-Element-Permutation aus der 3-Element-Rotation, dann eine 5-Element-Permutation aus 4 erstellen - Element Permutation, und so weiter, bis Sie N Elemente erreichen.
z. Die 3-Element-Rotation ist wie folgt:
%Vor%Die 4-Element-Permutation verwendet wiederholt die 3-Element-Drehung, abwechselnd mit einer Drehung, in der das vierte Element gedreht wird:
%Vor% (Dabei ist < die Position eines Elements, das gedreht wird, und = ist die Position eines Elements, das an seinem Platz bleibt.)
Die 5-Element-Permutation wiederholt die 4-Element-Permutation, abwechselnd mit einer Drehung, in der das fünfte Element gedreht wird:
%Vor%
Für jeden Schritt von N-1 bis N Elemente gibt es mehrere Optionen, jede mit ihrem eigenen Endzustand. Jeder Schritt ist somit durch N-1-Rotationen definiert, und zusammen definieren sie eine N-Element-Permutation; z.B. Für das obige Beispiel:
%Vor%
Sie werden in den obigen Beispielen sehen, dass die 4-Element-Permutation nicht 3 identische Rotationen verwendet, sondern stattdessen <<=< , wieder <<=< und schließlich =<<< ; das ist, weil nicht jede Kombination von möglichen Umdrehungen eine richtige Permutation schafft.
Um herauszufinden, welche Rotationen Sie für eine N-Element-Permutation verwenden können, sehen Sie sich den Endzustand der N-1-Element-Permutation an und sehen Sie, welche Zyklen enthalten sind, z. B .:
Permutation 0123 -> 1320 hat zwei Zyklen: [031] und [2] , da Position 0 auf Position 3, Position 3 auf Position 1 und Position 1 auf Position 0, Position 2 auf Position
Permutation 0123 -> 3210 hat zwei Zyklen: [03] und [12] , weil 0 und 3 die Plätze wechseln und 1 und 2 die Plätze wechseln.
Fall: mehrere Zyklen
Um eine N-Element-Permutation aus einer N-1-Element-Permutation zu erstellen, müssen Sie zwei Elemente aus den ersten N-1-Elementen mit dem N-ten Element drehen. Überprüfe, welche Zyklen die N-1-Element-Permutation hat, und wähle Rotationspunkte an Position 0 und an einer Position in einem zweiten Zyklus aus. Wiederholen Sie diese Drehung so oft, wie es Elemente im zweiten Zyklus gibt, und verschieben Sie dann den zweiten Punkt an eine Position im dritten Zyklus (wenn es einen gibt), und wiederholen Sie dies so oft wie es Elemente im dritten Zyklus gibt, und bald. Wenn alle Zyklen verwendet wurden, wiederholen Sie die letzte Drehung wie erforderlich.
Ein Beispiel wird dies verdeutlichen:
%Vor%Wie Sie feststellen werden, bleibt die Rotation bei 2 Zyklen gleich:
%Vor%Fall: ein Zyklus
Finde zwei Positionen X und Y, wobei X links von Y liegt, die N-1 Permutation bewegt sich X zu Y und Y ist nicht die am weitesten rechts liegende Position in der N-1 Permutation. Dann drehen Sie die Positionen X und Y mit dem N-ten Element wiederholt und für den letzten Schritt drehen Sie Y und die Position ganz rechts.
Auch hier wird ein Beispiel dies verdeutlichen:
%Vor%Es gibt einen Kantenfall, wenn die N-1-Permutation aus 1-Positionsverschiebungen in der gleichen Richtung wie die Rotation besteht; Wechseln Sie in diesem Fall zwischen den Positionen 0 und 1 und den Positionen 1 und 2:
%Vor%
Hier ist ein Beispiel für Permutationen von bis zu 10 Elementen; Es gibt viele Optionen, aber diese zeigt ein interessantes sich wiederholendes Muster ausgehend von 7 Elementen (vergleiche die Rotationen, die für 7 und 9 Elemente und für 8 und 10 Elemente verwendet werden, und auch den Endzustand für 7 und 9 Elemente):
%Vor% %Vor% %Vor% %Vor% %Vor% %Vor% %Vor% %Vor%
Das Erzeugen von Permutationen erfolgt, indem zuerst ausgewählt wird, welche Rotationen zu verwenden sind, und dann die Rotationen mit der folgenden Sequenz ausgeführt werden, wobei jede dritte 3 durch eine 4 ersetzt wird, jede vierte 4 durch eine 5 ersetzt wird, jede fünfte 5 wird ersetzt um eine 6 und so weiter:
3,3,4,3,3,4,3,3,4,3,3,5,3,3,4,3,3,4,3,3,4,3,3,5 , 3,3,4,3,3,4,3,3,4,3,3,5,3,3,3,3,4,3,3,4,3,3,5,3 , 3,4,3,3,4,3,3,4,3,3,6 ...
ist ähnlich wie Ehrlichs Sequenz, indem man die ersten 2 Rotationen benutzt, um die 3 Permutationen von 3 Elementen zu erzeugen, oder die ersten 11 für die 12 Permutationen für 4 Elemente, oder die ersten 59 für die 60 Permutationen von 5 Elemente, oder allgemein: N! / 2-1 Rotationen, um N! / 2 Permutationen zu erzeugen.
(Update: Für eine Implementierung, siehe meine andere Antwort auf diese Frage.)
Wie in der Frage und den Kommentaren erwähnt wurde, kann nur die Hälfte der möglichen Permutationen unter Verwendung einer 3-Element-Rotation erzeugt werden. Jede Permutation, die mit der obigen Methode erzeugt wird, hat eine unerreichbare Companion-Permutation, die erzeugt werden kann, indem die ersten zwei Elemente umgeschaltet werden, z.B.:
%Vor%Tags und Links algorithm permutation combinatorics