Superpermutation

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen
Verteilung von Permutationen in einer Superpermutation mit 3 Symbolen, C=rot, B=blau, A=grün

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 1≤ die kleinste Superpermutation die Länge , also , hat. So gibt es beispielsweise 6 Permutationen für die drei Elemente , nämlich , , , , und ; und eine kleinste Superpermutation, welche alle diese Permutationen beinhaltet, hat eine Länge von 9 Zeichen: .

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: “The minimal length is still unknown for , but we can show that for all it is strictly less than the conjectured length […]”.[1]

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.[2] Robin Houston, Jay Pantone und Vince Vatter haben am 25. Oktober 2018 einen vollständigen Beweis dessen in der Datenbank OEIS veröffentlicht.[3]

  • Daniel A. Ashlock, Jenett Tillotson: Construction of small superpermutations and minimal injective superstrings. In: Congressus Numerantium. 1993, S. 91–98, Zbl 0801.05004.
  • Nathaniel Johnston: Non-uniqueness of minimal superpermutations. In: Discrete Mathematics. Band 313, Nr. 14, 28. Juli 2013, S. 1553–1557, doi:10.1016/j.disc.2013.03.024, arxiv:1303.4150 (Zbl 1368.05004).
  • Robin Houston: Tackling the Minimal Superpermutation Problem. 21. August 2014, arxiv:1408.5108.

Einzelnachweise

[Bearbeiten | Quelltext bearbeiten]
  1. Robin Houston: Tackling the Minimal Superpermutation Problem. (PDF; englisch).
  2. /sci/ - Science & Math. Abgerufen am 2. Januar 2019.
  3. Anonymous 4chan Poster, Robin Houston, Jay Pantone, Vince Vatter: A lower bound on the length of the shortest superpattern. (PDF; 91,5 kB) In: OEIS. 25. Oktober 2018, S. 3, archiviert vom Original (nicht mehr online verfügbar) am 2. Januar 2018; abgerufen am 2. Januar 2019 (englisch).