Superpermutation

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

Eine Superpermutation von n Zeichen ist in der Kombinatorik eine Zeichenkette, die jede mögliche Permutation, also Kombination, dieser n Zeichen als Zeichenkette beinhaltet.

Es wurde gezeigt, dass für 1≤ n ≤ 5 die kleinste Superpermutation die Länge 1! + 2! + … + n!, also , hat. So gibt es beispielsweise für die drei Elemente {A, B, C} 6 Permutationen, nämlich ABC, ACB, BAC, BCA, CAB und CBA; und eine kleinste Superpermutation, welche alle diese Permutationen beinhaltet, hat eine Länge von 9 Zeichen: CBACBCABC.

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 n = 6 wurde 2014 eine kürzere Superpermutation als gefunden. Anstelle einer Länge von 873 Zeichen wurden für n = 6 nur 872 Zeichen benötigt. Es wird daher erwartet, dass für n ≥ 6 gilt, dass maximal eine Länge von (1! + 2! + … + n!) - 1 für die kürzeste Superpermutation benötigt wird: “The minimal length is still unknown for n ≥ 6, but we can show that for all n ≥ 6 it is strictly less than the conjectured length […]”.[1]

Literatur[Bearbeiten | Quelltext bearbeiten]

  • 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.

Weblinks[Bearbeiten | Quelltext bearbeiten]

Einzelnachweise[Bearbeiten | Quelltext bearbeiten]

  1. Robin Houston: Tackling the Minimal Superpermutation Problem (PDF)