Steinhaus-Johnson-Trotter-Algorithmus

Der Steinhaus-Johnson-Trotter-Algorithmus oder der Johnson-Trotter-Algorithmus, auch einfache Änderungen genannt, ist ein Algorithmus, der nach Hugo Steinhaus, Selmer M. Johnson und Hale Trotter benannt ist und alle Permutationen von $n$ Elementen erzeugt. Jede Permutation in der von ihr erzeugten Sequenz unterscheidet sich von der vorherigen Permutation durch Vertauschen zweier benachbarter Elemente der Sequenz. Entsprechend findet dieser Algorithmus einen Hamiltonweg im Permutaeder.

Der Hamiltonpfad im Cayleygraph der symmetrischen Gruppe, die mit dem Steinhaus-Johnson-Trotter-Algorithmus erzeugt wurde

Die Permutationen von vier Elementen, deren element-basierte Vertauschungs-Sätze (Sätze von Element-Paaren außerhalb ihrer natürlichen Reihenfolge), Vertauschungs-Vektoren und Vertauschungs-Zahlen.

Die Vertauschungs-Sätze bilden einen Gray-Code, also auch die Vertauschungs-Vektoren (Summen der aufsteigenden Diagonalen in den Dreiecken) und die Vertauschungs-Zahlen.

Die Zahlen auf der linken Seite sind die umgekehrten kolexikografischen Indizes der Permutationen (vergleiche: Liste in natürlicher Reihenfolge) und bilden Zeile 4 des Dreiecks Folge A280319 in OEIS.

Die Vertauschungs-Sätze von Permutationen, die 12 Stellen voneinander entfernt sind, sind Komplemente.

Polardiagramm aller Permutationen $n=4$ generiert durch den Steinhaus-Johnson-Trotter-Algorithmus, bei dem jede Permutation farbcodiert ist (1 = blau, 2 = grün, 3 = gelb, 4 = rot)

Diese Methode war bereits den englischen Change-Ringern des 17. Jahrhunderts bekannt und Robert Sedgewick nennt sie 1977 „den vielleicht bekanntesten Permutations-Aufzählungsalgorithmus“. Er ist nicht nur einfach und rechnerisch effizient, sondern hat auch den Vorteil, dass nachfolgende Berechnungen der von ihm erzeugten Permutationen beschleunigt werden können, da diese Permutationen einander so ähnlich sind.

Rekursive Struktur

Die Folge von Permutationen für eine gegebene Anzahl $n$ kann aus der Folge von Permutationen für $n-1$ gebildet werden, indem die Zahl $n$ an jeder möglichen Position in jeder der kürzeren Permutationen platziert wird. Wenn die Permutation für $n-1$ Elemente eine gerade Permutation ist (wie dies für die ersten, dritten usw. Permutationen in der Sequenz der Fall ist), wird die Zahl $n$ an allen möglichen Positionen in absteigender Reihenfolge von $n$ bis 1 platziert. Wenn die Permutation für $n-1$ Elemente ungerade ist, wird die Zahl $n$ in aufsteigender Reihenfolge an allen möglichen Positionen platziert.

Daher gilt: Aus der einzelnen Permutation für ein Element

1

kann man die Zahl 2 an jeder möglichen Position in absteigender Reihenfolge platzieren, um eine Liste von zwei Permutationen auf zwei Elementen zu bilden:

1 2

2 1

Dann kann man die Zahl 3 in jeweils drei verschiedenen Positionen für diese beiden Permutationen in absteigender Reihenfolge für die erste Permutation 1 2 und dann in aufsteigender Reihenfolge für die Permutation 2 1 platzieren:

1 2 3

1 3 2

3 1 2

3 2 1

2 3 1

2 1 3

Auf der nächsten Rekursionsstufe würde die Zahl 4 in absteigender Reihenfolge in 1 2 3, in aufsteigender Reihenfolge in 1 3 2, in absteigender Reihenfolge in 3 1 2 usw. platziert. Das gleiche Platzierungsmuster, das zwischen absteigender und aufsteigender Platzierung von $n$ wechselt, gilt für jeden größeren Wert von $n$. Auf diese Weise unterscheidet sich jede Permutation von der vorherigen entweder durch die Bewegung von $n$ um jeweils eine Position oder durch einen Tausch von zwei kleineren Zahlen, die von der vorherigen Folge kürzerer Permutationen übernommen wurden. In beiden Fällen ist dieser Unterschied nur die Vertauschung zweier benachbarter Elemente. Wenn $n>1$ ist, unterscheiden sich das erste und das letzte Element der Sequenz auch nur in zwei benachbarten Elementen (den Positionen der Zahlen 1 und 2), wie durch Induktion gezeigt werden kann.

Obwohl diese Sequenz durch einen rekursiven Algorithmus erzeugt werden kann, der die Folge kleinerer Permutationen konstruiert und dann alle möglichen Einfügungen der größten Zahl in die rekursiv erzeugte Folge durchführt, vermeidet der tatsächliche Steinhaus-Johnson-Trotter-Algorithmus eine Rekursion und berechnet stattdessen dieselbe Folge von Permutationen durch eine iterative Methode.

Es gibt eine äquivalente und konzeptionell etwas einfachere Definition der Steinhaus-Johnson-Trotter-Reihenfolge von Permutationen über den folgenden „gierigen“ Algorithmus: Wir beginnen mit der Identitäts-Permutation $12\dots n$. Jetzt vertauschen wir wiederholt den größtmöglichen Eintrag mit dem Eintrag links oder rechts, sodass in jedem Schritt eine neue Permutation erstellt wird, die in der Liste der Permutationen zuvor noch nicht existierte. Zum Beispiel beginnen wir in dem Fall $n=3$ mit 123, dann tauschen wir 3 mit seinem linken Nachbarn und erhalten 132. Wir tauschen dann 3 mit seinem linken Nachbarn 1, da das Tauschen von 3 mit seinem rechten Nachbarn 2 wieder 123 ergeben würde, was wir zuvor schon erzeugt haben, also kommen wir zu 312 usw. Die Richtung der Vertauschung (links oder rechts) wird in diesem Algorithmus immer eindeutig vorgegeben.

Algorithmus

Wie von Johnson beschrieben, führt der Algorithmus zum Erzeugen der nächsten Permutation aus einer gegebenen Permutation π die folgenden Schritte aus:

• für jedes i von 1 bis n sei x_i die Position, an der der Wert i in die Permutation π gesetzt ist. Wenn die Reihenfolge der Zahlen von 1 bis i − 1 in der Permutation π eine gerade Permutation ist, setze y_i = x_i − 1; andernfalls setze y_i = x_i + 1.
• finde die größte Zahl i, für die y_i eine gültige Position in der Permutation π definiert, die eine Zahl kleiner als i enthält. Tausche die Werte an den Positionen x_i und y_i aus.

Wenn keine Zahl i gefunden werden kann, die die Bedingungen des zweiten Schritts des Algorithmus erfüllt, hat der Algorithmus die endgültige Permutation der Sequenz erreicht und endet. Diese Prozedur kann in $O(n)$ Zeit pro Permutation implementiert werden.

Trotter gibt eine alternative Implementierung eines iterativen Algorithmus für dieselbe Sequenz in leicht kommentierter ALGOL 60-Notation an.

Da diese Methode Permutationen generiert, die zwischen gerade und ungerade wechseln, kann sie leicht geändert werden, um nur die geraden Permutationen oder nur die ungeraden Permutationen zu generieren: Um die nächste Permutation derselben Parität aus einer bestimmten Permutation zu generieren, wenden Sie einfach dieselbe Prozedur zweimal an.

Beschleunigung durch Even

Eine nachfolgende Verbesserung durch Shimon Even verbessert die Laufzeit des Algorithmus, indem zusätzliche Informationen für jedes Element in der Permutation gespeichert werden: seine Position und eine Richtung (positiv, negativ oder Null), in die es sich gerade bewegt (im Wesentlichen sind dies die gleichen Informationen, die unter Verwendung der Parität der Permutation in Johnsons Version des Algorithmus berechnet wurden). Anfangs ist die Richtung der Zahl 1 Null, und alle anderen Elemente haben eine negative Richtung:

1 −2 −3

Bei jedem Schritt findet der Algorithmus das größte Element mit einer Richtung ungleich Null und tauscht es in die angegebene Richtung aus:

1 −3 −2

Wenn dies dazu führt, dass das ausgewählte Element die erste oder letzte Position innerhalb der Permutation erreicht, oder wenn das nächste Element in derselben Richtung größer als das ausgewählte Element ist, wird die Richtung des ausgewählten Elements auf Null gesetzt:

3 1 −2

Nach jedem Schritt werden für alle Elemente, die größer als das ausgewählte Element sind (das zuvor die Richtung Null hatte), die Richtungen so eingestellt, dass sie eine Bewegung in Richtung des ausgewählten Elements anzeigen. Das heißt, positiv für alle Elemente zwischen dem Beginn der Permutation und dem ausgewählten Element und negativ für Elemente zum Ende hin. In diesem Beispiel wird die Nummer 3 nach dem Bewegen der Nummer 2 erneut mit einer Richtung markiert:

+3 2 1

Die verbleibenden zwei Schritte des Algorithmus für $n=3$ sind:

2 +3 1

2 1 3

Wenn keine Zahl mehr markiert ist, wird der Algorithmus beendet.

Dieser Algorithmus benötigt die Zeit $O(i)$ für jeden Schritt, in dem die größte zu bewegende Zahl $n-i+1$ ist. Somit benötigen die Vertauschungen mit der Zahl $n$ nur eine konstante Zeit. Da diese Vertauschungen für alle bis auf einen $1/n$-Bruchteil aller Vertauschungen greifen, die durch den Algorithmus durchgeführt werden, ist die durchschnittliche Zeit pro Permutation ebenfalls konstant, wenn auch eine kleine Anzahl von Permutationen eine größere Zeit in Anspruch nimmt.

Eine komplexere schleifenlose Version derselben Prozedur ermöglicht es, sie in jedem Fall in konstanter Zeit pro Permutation durchzuführen. Die Änderungen, die erforderlich sind, um Schleifen aus dem Verfahren zu entfernen, machen es in der Praxis jedoch langsamer.

Geometrische Interpretation

Die Menge aller Permutationen von $n$ Elementen kann geometrisch durch einen Permutaeder dargestellt werden. Das ist das Polytop, das aus der konvexen Hülle von $n!$ Vektoren gebildet wird, eben den Permutationen des Vektors $(1,2,\dots ,n)$. Obwohl auf diese Weise im $n$-dimensionalen Raum definiert, handelt es sich tatsächlich um ein $(n-1)$-dimensionales Polytop. Beispielsweise ist das Permutaeder auf vier Elementen ein dreidimensionales Polyeder, eben der Oktaederstumpf. Wenn jede Ecke des Permutaeders durch die inverse Permutation zu der durch seine Eck-Koordinaten definierten Permutation gekennzeichnet ist, beschreibt die resultierende Beschriftung einen Cayley-Graphen der symmetrischen Gruppe von Permutationen auf $n$ Elementen, wie sie durch die Permutationen erzeugt werden, die benachbarte Elementpaare austauschen. Somit entsprechen jeweils zwei aufeinander folgende Permutationen in der vom Steinhaus-Johnson-Trotter-Algorithmus erzeugten Sequenz auf diese Weise zwei Eckpunkten, die die Endpunkte einer Kante im Permutaeder bilden, und die gesamte Sequenz von Permutationen beschreibt einen Hamilton-Pfad im Permutaeder. Ein Pfad, der genau einmal durch jeden Eckpunkt verläuft. Wenn die Folge von Permutationen durch Hinzufügen einer weiteren Kante von der letzten Permutation zur ersten in der Folge abgeschlossen ist, ist das Ergebnis stattdessen ein Hamilton-Zyklus.

Beziehung zu Gray-Codes

Ein Gray-Code für Zahlen in einem bestimmten Stellenwertsystem ist eine Sequenz, die jede Zahl bis zu einer bestimmten Grenze genau einmal enthält, sodass sich jedes Paar aufeinander folgender Zahlen in einer einzelnen Ziffer um eins unterscheidet. Die $n!$ Permutationen der $n$ Zahlen von 1 bis n können in eine Eins-zu-Eins-Beziehung mit dem $n!$ Zahlen von 0 bis $n!-1$ gesetzt werden, indem jede Permutation mit der Folge von Zahlen c_i verbunden wird, die die Anzahl der Positionen in der Permutation zählt, die rechts vom Wert i liegen und einen Wert kleiner als i enthalten (d. h. die Anzahl der Vertauschungen für die i der größere der beiden getauschten Werte ist) und dann diese Sequenzen als Zahlen im fakultätsbasiertem Zahlensystem interpretiert werden, d. h. im Zahlensystem mit gemischten Basen mit den Basen (1, 2, 3, 4, …). Zum Beispiel würde die Permutation (3, 1, 4, 5, 2) die Werte c₁ = 0, c₂ = 0, c₃ = 2, c₄ = 1 und c₅ = 1 ergeben. Die Folge von diesen Werte (0, 0, 2, 1, 1) gibt folgende Zahl an:

0 × 0! + 0 × 1! + 2 × 2! + 1 × 3! + 1 × 4! = 34.

Aufeinander folgende Permutationen, in der vom Steinhaus-Johnson-Trotter-Algorithmus erzeugten Sequenz, weisen eine Anzahl von Vertauschungen auf, die sich um eins unterscheiden und einen Gray-Code für das fakultätsbasierte Zahlensystem bilden.

Allgemeiner gesagt, haben Forscher von kombinatorischen Algorithmen einen Gray-Code für eine Reihe von kombinatorischen Objekten definiert, der eine Reihenfolge für die Objekte ist, in der sich jeweils zwei aufeinander folgende Objekte auf minimal mögliche Weise unterscheiden. In diesem verallgemeinerten Sinne generiert der Steinhaus-Johnson-Trotter-Algorithmus einen Gray-Code für die Permutationen selbst.

Geschichte

Der Algorithmus ist nach Hugo Steinhaus, Selmer M. Johnson und Hale Trotter benannt. Johnson und Trotter entdeckten den Algorithmus Anfang der 1960er Jahre unabhängig voneinander. Ein Buch von Steinhaus, das ursprünglich 1958 veröffentlicht und 1963 ins Englische übersetzt wurde, beschreibt ein verwandtes Rätsel, bei dem alle Permutationen durch ein System von Teilchen erzeugt werden, die sich jeweils mit konstanter Geschwindigkeit entlang einer Linie bewegen und ihre Positionen vertauschen, wenn ein Teilchen ein anderes überholt. Für $n>3$ ist keine Lösung möglich, da die Anzahl der Vertauschungen weitaus geringer ist als die Anzahl der Permutationen. Der Steinhaus-Johnson-Trotter-Algorithmus beschreibt jedoch die Bewegung von Teilchen mit nicht konstanten Geschwindigkeiten, die alle Permutationen erzeugen.

Außerhalb der Mathematik war diese Methode schon viel länger als eine Methode zum Ändern des Tons von mehreren Kirchenglocken bekannt: Sie gibt ein Verfahren an, mit dem eine Reihe von Glocken durch alle möglichen Permutationen geläutet werden kann, wobei nur zwei Glocken pro Änderung getauscht werden. Diese sogenannten „einfachen Veränderungen“ wurden bereits 1621 für vier Glocken aufgezeichnet, und ein Buch von Fabian Stedman aus dem Jahr 1677 listet die Lösungen für bis zu sechs Glocken auf. In jüngerer Zeit haben sich Glöckner an die Regel gehalten, dass keine Glocke in drei aufeinander folgenden Permutationen an derselben Position bleiben darf. Da dies die Regel der „einfachen Änderungen“ verletzt, wurden andere Strategien entwickelt, die mehrere Glocken pro Änderung austauschen.

Siehe auch

• Heap-Algorithmus
• Fisher-Yates-Verfahren