超排列
在組合數學中，n個符號的超排列（英語：Superpermutation）是一個字符串，使得n個符號的所有排列均為它的子串。這些子串可以互相重疊。對於任意一個指定的n，超排列的長度存在一個最小值，最短的超排列稱為最小超排列。
在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]
參考文獻
[編輯]- ^ Anonymous. Permutations Thread III. Warosu, a 4chan archive. 2011-09-17 [2018-10-27]. （原始內容存檔於2018-10-25）.
- ^ 崔天也. 动漫改变数学？困扰数学界25年的谜题疑似因讨论动漫被解. 環球網. 2018-10-27 [2018-10-27]. （原始內容存檔於2019-08-07）.
- ^ Griggs, Mary Beth. An anonymous 4chan post could help solve a 25-year-old math mystery. The Verge. [2018-10-27]. （原始內容存檔於2018-10-26）.
- ^ Houston, Robin. A curious situation. The best known lower bound... (1054637891085918209). Twitter. [2018-10-27]. （原始內容存檔於2018-10-26） （英語）.
- ^ Anomymous 4chan poster; Houston, Robin; Pantone, Jay; Vatter, Vince. A lower bound on the length of the shortest superpattern (PDF). OEIS. 2018-10-25 [2018-10-27]. （原始內容存檔 (PDF)於2018-10-27）.
- ^ Aaron, Williams. Hamiltonicity of the Cayley Digraph on the Symmetric Group Generated by σ = (1 2 ... n) and τ = (1 2). arXiv:1307.2549v3 .
- ^ Egan, Greg. Superpermutations. 2018-10-20 [2018-10-27]. （原始內容存檔於2018-10-25）.
外部連結
[編輯]- The Minimal Superpermutation Problem - Nathaniel Johnston's blog （頁面存檔備份，存於網際網路檔案館）
- Grime, James. Superpermutations - Numberphile. Brady Haran. [2018-02-01]. （原始內容 (video)存檔於2021-05-10）.