超排列

在组合数学中，n个符号的超排列（）是一个字符串，使得n个符号的所有排列均为它的子串。这些子串可以互相重叠。对于任意一个指定的n，超排列的长度存在一个最小值，最短的超排列称为最小超排列。

在1≤n≤5时，n个符号的最小超排列的长度是1!+2!+...+n!，分别是1、3、9、33和153，与之对应的字符串分别是1、121、123121321、123412314231243121342132413214321，以及：
123451234152341253412354123145231425314235142315423124531243
512431524312543121345213425134215342135421324513241532413524
132541321453214352143251432154321

上界和下界
下界
在2011年9月，贴图讨论版网站4chan上的一个匿名用户（Lower Bounds）证明，n（n≥2）个符号的最小超排列的长度至少为 n! +(n-1)! +(n-2)! + n -3。4chan中讨论最小超排列问题的最初目的是解决如何在最短时间内看完电视动画《凉宫春日的忧郁》2006年版共14集的全部可能组合（它在上映时是打乱顺序播出的），相当于求n =14的最小超排列，因此最小超排列问题也被称为凉宫春日问题。

在2018年10月，计算机科学家罗宾·休斯顿（Robin Houston）在推特上介绍了这一证明，因此引起了公众的兴趣。2018年10月25日，罗宾·休斯顿、杰伊·潘托内（Jay Pantone）和文森·瓦特（Vince Vatter）整理并在OEIS上公布了匿名用户的证明，第一作者为“Anonymous 4chan Poster”。

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

评论 (0)