2016-03-18 The Usual Way

Eine Permutationssequenz besteht aus einer Reihenfolge von Zusänden, die jeweils durch Vertauschung zweier Elemente auseinander hervorgehen. In einer Permutationssequenz dar kein Zustand doppelt vorkommen oder fehlen. Für n Elemente gibt es (n*(n-1))/2 solcher Zustände.
Ausgangszustand: 1234
mögliche Fogezustände: 2134 3214 4231 1324 432 1243
Eine Standard-Permutationssequenz gibt eine feste Regel für die Abarbeitung der einzelnen Zustände vor. Insoweit ist der Ablauf einer Standard-Permutationssequenz deterministisch.
Das obige Beispiel zeigt eine Vertauschung von Indices; in den
Clips werden diesen Indices Objekte zugeordnet.
Beim Algorithmus von Steinhaus-Johnson-Trotter sind dies:
1 A
2 B
3 C
4 _
In diesem Algorithmus wird ein Führungsobjekt, im Clip durch _
markiert, zunächst von hinten nach vorne durchgeschoben.
Hat dieses Führungsobjekt den ersten Platz erreicht, so ruht dies für eine Phase, und mit dem Objekt mit dem nächstniedrigen Index, in diesem Fall C, wird gleichermassen verfahren.
Der Algorithmus für n Objekte besteht somit aus n-1 verschachtelten Schleifen. Dabei ist die Kennzahl der inneren Schleife jeweils um 1 geringer als die der äusseren Schleife.
Ist die vorderste Position erreicht, so wandert das Führungsobjekt in die entgegengesetzte Richtung, also von
vorne nach hinten. Das lässt sich im Clip durch Verfolgung des Zeichens _ sehr gut nachvollziehen.
Nun können Permutationszustände auch lexikalisch angeordnet werden. Dabei wird die Indexdarstellung als n-stellige Zahl begriffen, und diese Zahlen werden der Grösse nach sortiert und
mit einer Ordnungsnummer versehen:
01 1234
02 1243
03 1324
04 1342
05 1423
06 1432
07 2134 usw.
Die Umsetzung der Indexdarstellungen in Ordnungsnummern bedarf keiner Tabelle, sondern ist durch einen unschwierigen
Algorithmus zu bewältigen. Im Anzeigefeld auf der rechten Seite werden bearbeitete Indexdarstellungen farblich markiert.
Verfolgt man den Weg des Führungsobjektes, so ergibt sich eine Charakteristik, welche man so darstellen kann: \/\/\/.
Beim anderen Algorithmus, welche ich als "Rotating" bezeichnen will, ergibt sich folgende Charakteristik: / / /\\\. Würde nach drei Rotationen weiter in die selbe Richtung rotiert, so würde wieder der Ausgangszustand erreicht. Also pausiert das Führungsobjekt, und es erfolgt die Rotation der inneren Schleife, deren Kennzahl um 2 geringer als die Kennzahl der äusseren Schleife ist. Bei nur vier Objekten freilich ist die innere Schleife nur ein einfaches Toggling.
Der Aufwand bei der Programmierung ist beim Rotating etwas grösser als bei Steinhaus-Johnson-Trotter - wohl ein Grund, weswegen zumeist Steinhaus-Johnson-Trotter der Vorzug gegeben wird