超排列

在組合數學中，n個符號的超排列（英語：Superpermutation）是一個字符串，使得n個符號的所有排列均為它的子串。這些子串可以互相重疊。對於任意一個指定的n，超排列的長度存在一個最小值，最短的超排列稱為最小超排列。

3個符號的超排列組合

在1≤n≤5時，n個符號的最小超排列的長度是1!+2!+...+n!，分別是1、3、9、33和153（OEIS數列A180632），與之對應的字符串分別是1、121、123121321、123412314231243121342132413214321，以及：

123451234152341253412354123145231425314235142315423124531243
512431524312543121345213425134215342135421324513241532413524
132541321453214352143251432154321

上界和下界

下界

在2011年9月，貼圖討論版網站4chan上的一個匿名用戶（Lower Bounds）證明，n（n≥2）個符號的最小超排列的長度至少為 n! +(n-1)! +(n-2)! + n -3^[1]。4chan中討論最小超排列問題的最初目的是解決如何在最短時間內看完電視動畫《涼宮春日的憂鬱》2006年版共14集的全部可能組合（它在上映時是打亂順序播出的），相當於求n =14的最小超排列^[2]。在2018年10月，計算機科學家羅賓·休斯頓（Robin Houston）在推特上介紹了這一證明，因此引起了公眾的興趣^[3][4] 。2018年10月25日，羅賓·休斯頓、傑伊·潘托內（Jay Pantone）和文森·瓦特（Vince Vatter）整理並在OEIS上公布了匿名用戶的證明^[5]。

上界

2018年10月20日，格雷格·伊根在接受阿隆·威廉士（Aaron Williams）的建議，通過對稱群的凱萊圖建立哈密頓圖的方式^[6]，設計了一種產生長度為n! +(n-1)! +(n-2)! +(n-3)! + n -3的超排列的算法^[7] 。

延伸閱讀

• Ashlock, Daniel A.; Tillotson, Jenett, Construction of small superpermutations and minimal injective superstrings, Congressus Numerantium, 1993, 93: 91–98, Zbl 0801.05004
• Johnston, Nathaniel, Non-uniqueness of minimal superpermutations, Discrete Mathematics, 2013-07-28, 313 (14): 1553–1557 [2014-03-16], Zbl 1368.05004, arXiv:1303.4150 , doi:10.1016/j.disc.2013.03.024, （原始內容存檔於2021-02-27）
• Houston, Robin, Tackling the Minimal Superpermutation Problem, 2014-08-21, arXiv:1408.5108  [math.CO]