mini|upright=1.1|Verteilung von Permutationen in einer Superpermutation mit 3 Symbolen ➊, ➋ und ➌ Eine Superpermutation von Zeichen ist in der Kombinatorik eine Zeichenkette, die jede mögliche Permutation, also Kombination, dieser Zeichen als Zeichenkette beinhaltet.
Es wurde gezeigt, dass für die kleinste Superpermutation die Länge hat.
So gibt es für die drei Elemente mit , , , , und insgesamt 6 Permutationen. Die kleinste Superpermutation, die all diese Permutationen beinhaltet, ist mit genau 9 Zeichen lang.
Die ersten fünf Superpermutationen haben die Längen 1, 3, 9, 33 und 153. Die Zeichenketten dieser Permutationen sehen beispielsweise so aus: 1 121 123121321 123412314231243121342132413214321 123451234152341253412354123145231425314235142315423124531243512431524312543121345213425134215342135421324513241532413524132541321453214352143251432154321.
Für eine Zeichenmenge von wurde 2014 eine kürzere Superpermutation als gefunden: Anstelle einer Länge von 873 Zeichen wurden für nur 872 Zeichen benötigt. Es wird daher erwartet, dass für gilt, dass maximal eine Länge von für die kürzeste Superpermutation benötigt wird: .
Auf dem Imageboard 4chan wurde am 27. September 2011 von einem anonymen Nutzer nachgewiesen, dass die kürzeste Superpermutation für eine Länge von mindestens hat. Robin Houston, Jay Pantone und Vince Vatter haben am 25. Oktober 2018 einen vollständigen Beweis dessen in der Datenbank OEIS veröffentlicht.
Die Ausgangsfrage behandelte die Anime-Fernsehserie Die Melancholie der Haruhi Suzumiya, deren 14 Episoden eine non-lineare Geschichte erzählen, die in verschiedenen Reihenfolgen Sinn ergeben kann. Ein User wollte wissen, in welcher Reihenfolge man denn nun die Serie schauen müsse, um in kürzester Zeit alle möglichen Reihenfolgen gesehen zu haben.
Literatur Daniel A. Ashlock, Jenett Tillotson: Construction of small superpermutations and minimal injective superstrings. In: Congressus Numerantium. 1993, S. 91–98, Zbl 0801.05004.
Weblinks The Minimal Superpermutation Problem – Nathaniel Johnston’s blog
Einzelnachweise
Kategorie:Permutationstheorie