跳至內容

超排列

本頁使用了標題或全文手工轉換
維基百科,自由的百科全書
3個符號的超排列組合

組合數學中,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)證明,nn≥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]

延伸閱讀

參考文獻

  1. ^ Anonymous. Permutations Thread III. Warosu, a 4chan archive. 2011-09-17 [2018-10-27]. (原始內容存檔於2018-10-25). 
  2. ^ 崔天也. 动漫改变数学?困扰数学界25年的谜题疑似因讨论动漫被解. 環球網. 2018-10-27 [2018-10-27]. (原始內容存檔於2019-08-07). 
  3. ^ Griggs, Mary Beth. An anonymous 4chan post could help solve a 25-year-old math mystery. The Verge. [2018-10-27]. (原始內容存檔於2018-10-26). 
  4. ^ Houston, Robin. A curious situation. The best known lower bound... (1054637891085918209). Twitter. [2018-10-27]. (原始內容存檔於2018-10-26) (英語). 
  5. ^ 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). 
  6. ^ Aaron, Williams. Hamiltonicity of the Cayley Digraph on the Symmetric Group Generated by σ = (1 2 ... n) and τ = (1 2). arXiv:1307.2549v3可免費查閱. 
  7. ^ Egan, Greg. Superpermutations. 2018-10-20 [2018-10-27]. (原始內容存檔於2018-10-25). 

外部連結