超排列

在组合数学中，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]

参考文献

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

外部链接

• The Minimal Superpermutation Problem - Nathaniel Johnston's blog （页面存档备份，存于互联网档案馆）
• Grime, James. Superpermutations - Numberphile. Brady Haran. [2018-02-01]. （原始内容 (video)存档于2021-05-10）.