» Tutti Frutti » Steinhaus-Johnson-Trotter algorithm » change ringers » Permutationssequenzen » mathematische Animationen
Ein Zitat aus Little Richard's Rock-'n'-Roll-Klassiker "Tutti Frutti" bildet den Auftakt zu diesem Film. <br />Zu dem Untertitel "Pemutionssequenzen" möchte ich zunächst den Algorithmus von Steinhaus, Johnson und Trotter erklären. <br />Dabei stehen die n Elemente einer Permutationssequenz nebeneinander, und die Permutationssequenz umfasst nun n! Kombinationen. Zwischen zwei aufeinanderfolgenden Kombination <br />steht nur die Vertauschung zweier benachbarter Elemente. Natürlich darf jede Kombination nur einmal vorkommen, und keine der Kombinationsmöglichkeiten darf fehlen. <br />Für die Grundzahl 3 lautet diese Permutationssequenz: <br />123 <br />132 <br />312 <br />Nun ist die 3 ganz links angelangt und kann nicht weiter nach links verschoben werden. <br />Stattdessen werden 1 und 2 miteinander vertauscht, und die 3 bewegt sich wieder nach rechts: <br />321 <br />231 <br />213 <br />Und nun schliesst der Zyklus durch eine abermalige Vertauschung von 1 und 2 ab: <br />123 <br /> <br />Es folgt jetzt die Permutationssequenz für 4 <br />Die Ausgangsstellung ist: <br />00 1234 <br />Analog zur Permutationssequenz für 3 wird die 4 nach links verschoben: <br />01 1243 <br />02 1423 <br />03 4123 <br />Nun ist wieder die innere Schleife dran, in welcher die 3 nach links verschoben wird: Die 4 wechselt die Richtung. <br />04 4132 <br />05 1432 <br />06 1342 <br />07 1324 <br />Den Rest ohne weitere Erklärungen <br />08 3124 <br />09 3142 <br />10 3412 <br />11 4312 <br /> <br />12 4321 <br />13 3421 <br />14 3241 <br />15 3214 <br /> <br />16 2314 <br />17 2341 <br />18 2431 <br />19 4231 <br /> <br />20 4213 <br />21 2413 <br />22 2143 <br />23 2134 <br />Mit: <br />24 1234 <br />ist die Permutationssequenz für 4 abgeschlossen. <br /> <br />Nun zum Grundmuster. Hier ist der Ablauf etwas anders. Die Elemente sind auf den Ecken eines Fünfecks angeordnet, und das Führungselement rotiert so lange, bis die Ausgangsstellung wieder erreicht würde. <br />Hier die Bezifferung der Elemente: <br />1 Avocado <br />2 Mango <br />3 Orange <br />4 Kaki <br />5 Paprika <br />Bei den nun folgenden Kombinationsmöglichkeiten berufe ich mich auf die Angaben des Permutationszähler. Das sind die Kästchen links und rechts unten: <br />0000 12345 <br />0001 21345 <br />0002 23145 <br />0003 23415 <br />0004 23451 <br /> <br />0010 13452 <br />0011 31452 <br />0012 34152 <br />0013 34512 <br />0014 34521 <br /> <br />0020 14523 <br />0021 41523 <br />0022 45123 <br />0023 45213 <br />0024 45231 <br /> <br />0030 15234 <br />0031 51234 <br />0032 52134 <br />0033 52314 <br />0034 52341 <br /> <br />Nun tritt die innere Schleife mit 3 Elementen auf den Plan: <br />0100 53241 <br />und die Richtung, in welcher die 1 rotiert, wird umgekehrt. <br /> <br />0101 53214 <br />0102 53124 <br />0103 53214 <br />0104 53241 <br /> <br />0110 13245 <br />Die innere Schleife läuft folgendermassen: <br />00__ _234_ <br />01__ _324_ <br />02__ _342_ <br /> <br />Beim nächsten inneren Wechsel werden zwei nichtbenachabrte Elemente vertauscht: <br />03__ _243_ <br />04__ _423_ <br />05__ _432_ <br />Und die innere Scheife schliesst sich: <br />00__ _234_ <br />Nun kann die 5er-Permutationssequenz als innere Schleife einer 7er-Permutationssequenz mit 5040 Kombinationen genommen werden, die 7er-Kombination als innere Schleife einer 9er-Permutationssequenz usw. usf.. <br />Es wäre noch viel mehr zu sagen, aber damit würde ich die von dailymotion zugelassene Zeichenanzahl überschreiten.
Ein Zitat aus Little Richard's Rock-'n'-Roll-Klassiker "Tutti Frutti" bildet den Auftakt zu diesem Film. <br />Zu dem Untertitel "Pemutionssequenzen" möchte ich zunächst den Algorithmus von Steinhaus, Johnson und Trotter erklären. <br />Dabei stehen die n Elemente einer Permutationssequenz nebeneinander, und die Permutationssequenz umfasst nun n! Kombinationen. Zwischen zwei aufeinanderfolgenden Kombination <br />steht nur die Vertauschung zweier benachbarter Elemente. Natürlich darf jede Kombination nur einmal vorkommen, und keine der Kombinationsmöglichkeiten darf fehlen. <br />Für die Grundzahl 3 lautet diese Permutationssequenz: <br />123 <br />132 <br />312 <br />Nun ist die 3 ganz links angelangt und kann nicht weiter nach links verschoben werden. <br />Stattdessen werden 1 und 2 miteinander vertauscht, und die 3 bewegt sich wieder nach rechts: <br />321 <br />231 <br />213 <br />Und nun schliesst der Zyklus durch eine abermalige Vertauschung von 1 und 2 ab: <br />123 <br /> <br />Es folgt jetzt die Permutationssequenz für 4 <br />Die Ausgangsstellung ist: <br />00 1234 <br />Analog zur Permutationssequenz für 3 wird die 4 nach links verschoben: <br />01 1243 <br />02 1423 <br />03 4123 <br />Nun ist wieder die innere Schleife dran, in welcher die 3 nach links verschoben wird: Die 4 wechselt die Richtung. <br />04 4132 <br />05 1432 <br />06 1342 <br />07 1324 <br />Den Rest ohne weitere Erklärungen <br />08 3124 <br />09 3142 <br />10 3412 <br />11 4312 <br /> <br />12 4321 <br />13 3421 <br />14 3241 <br />15 3214 <br /> <br />16 2314 <br />17 2341 <br />18 2431 <br />19 4231 <br /> <br />20 4213 <br />21 2413 <br />22 2143 <br />23 2134 <br />Mit: <br />24 1234 <br />ist die Permutationssequenz für 4 abgeschlossen. <br /> <br />Nun zum Grundmuster. Hier ist der Ablauf etwas anders. Die Elemente sind auf den Ecken eines Fünfecks angeordnet, und das Führungselement rotiert so lange, bis die Ausgangsstellung wieder erreicht würde. <br />Hier die Bezifferung der Elemente: <br />1 Avocado <br />2 Mango <br />3 Orange <br />4 Kaki <br />5 Paprika <br />Bei den nun folgenden Kombinationsmöglichkeiten berufe ich mich auf die Angaben des Permutationszähler. Das sind die Kästchen links und rechts unten: <br />0000 12345 <br />0001 21345 <br />0002 23145 <br />0003 23415 <br />0004 23451 <br /> <br />0010 13452 <br />0011 31452 <br />0012 34152 <br />0013 34512 <br />0014 34521 <br /> <br />0020 14523 <br />0021 41523 <br />0022 45123 <br />0023 45213 <br />0024 45231 <br /> <br />0030 15234 <br />0031 51234 <br />0032 52134 <br />0033 52314 <br />0034 52341 <br /> <br />Nun tritt die innere Schleife mit 3 Elementen auf den Plan: <br />0100 53241 <br />und die Richtung, in welcher die 1 rotiert, wird umgekehrt. <br /> <br />0101 53214 <br />0102 53124 <br />0103 53214 <br />0104 53241 <br /> <br />0110 13245 <br />Die innere Schleife läuft folgendermassen: <br />00__ _234_ <br />01__ _324_ <br />02__ _342_ <br /> <br />Beim nächsten inneren Wechsel werden zwei nichtbenachabrte Elemente vertauscht: <br />03__ _243_ <br />04__ _423_ <br />05__ _432_ <br />Und die innere Scheife schliesst sich: <br />00__ _234_ <br />Nun kann die 5er-Permutationssequenz als innere Schleife einer 7er-Permutationssequenz mit 5040 Kombinationen genommen werden, die 7er-Kombination als innere Schleife einer 9er-Permutationssequenz usw. usf.. <br />Es wäre noch viel mehr zu sagen, aber damit würde ich die von dailymotion zugelassene Zeichenanzahl überschreiten.
