超排列

在组合数学中，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月，计算机科学家罗宾·休斯顿在推特上介绍了这一证明，因此引起了公众的兴趣[3][4] 。2018年10月25日，罗宾·休斯顿、杰伊·潘托内和维森特·瓦特整理并在OEIS上公布了匿名用户的证明[5]。

上界

2018年10月20日，格雷格·伊根在接受阿隆·威廉姆斯的建议，通过对称群的凯莱图建立哈密顿图的方式[6]，设计了一种产生长度为n! +(n-1)! +(n-2)! +(n-3)! + n -3的超排列的算法[7] 。

延伸阅读

Ashlock, Daniel A.; Tillotson, Jenett, , Congressus Numerantium, 1993, 93: 91–98, Zbl 0801.05004
Johnston, Nathaniel, , 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, , 2014-08-21, arXiv:1408.5108  [math.CO]

参考文献

Anonymous. . Warosu, a 4chan archive. 2011-09-17 [2018-10-27]. （原始内容存档于2018-10-25）.
崔天也. . 环球网. 2018-10-27 [2018-10-27]. （原始内容存档于2019-08-07）.
Griggs, Mary Beth. . The Verge. [2018-10-27]. （原始内容存档于2018-10-26）.
Houston, Robin. . Twitter. [2018-10-27]. （原始内容存档于2018-10-26）（英语）.
Anomymous 4chan poster; Houston, Robin; Pantone, Jay; Vatter, Vince. (PDF). OEIS. 2018-10-25 [2018-10-27]. （原始内容存档 (PDF)于2018-10-27）.
Aaron, Williams. . arXiv:1307.2549v3 .
Egan, Greg. . 2018-10-20 [2018-10-27]. （原始内容存档于2018-10-25）.

外部链接

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

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[1] Anonymous. . Warosu, a 4chan archive. 2011-09-17 [2018-10-27]. （原始内容存档于2018-10-25）.

[2] 崔天也. . 环球网. 2018-10-27 [2018-10-27]. （原始内容存档于2019-08-07）.

[3] Griggs, Mary Beth. . The Verge. [2018-10-27]. （原始内容存档于2018-10-26）.

[4] Houston, Robin. . Twitter. [2018-10-27]. （原始内容存档于2018-10-26）（英语）.

[5] Anomymous 4chan poster; Houston, Robin; Pantone, Jay; Vatter, Vince. (PDF). OEIS. 2018-10-25 [2018-10-27]. （原始内容存档 (PDF)于2018-10-27）.

[6] Aaron, Williams. . arXiv:1307.2549v3 .

[7] Egan, Greg. . 2018-10-20 [2018-10-27]. （原始内容存档于2018-10-25）.