fbpx
维基百科

超排列

一月 29, 2023

在组合数学中，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月，计算机科学家罗宾·休斯顿在推特上介绍了这一证明，因此引起了公众的兴趣[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, Construction of small superpermutations and minimal injective superstrings, 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, 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. ^ 崔天也. . 环球网. 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. . Brady Haran. [2018-02-01]. （原始内容 (video)存档于2021-05-10）. 

一月 29, 2023
超排列, 在组合数学中, 个符号的, superpermutation, 是一个字符串, 使得n, 个符号的所有排列均为它的子串, 这些子串可以互相重叠, 对于任意一个指定的, 的长度存在一个最小值, 最短的称为最小, 个符号的最小的长度是1, 分别是1, 33和153, oeis數列a180632, 与之对应的字符串分别是1, 123121321, 123412314231243121342132413214321, 以及, 12345123415234125341235412314523142531423514. 在组合数学中 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 目录 1 上界和下界 1 1 下界 1 2 上界 2 延伸阅读 3 参考文献 4 外部链接上界和下界 编辑下界 编辑 在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 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 s 1 2 n and t 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 取自 https zh wikipedia org w index php title 超排列 amp oldid 74931005, 维基百科，wiki，书籍，书籍，图书馆，

文章

，阅读，下载，免费，免费下载，mp3，视频，mp4，3gp， jpg，jpeg，gif，png，图片，音乐，歌曲，电影，书籍，游戏，游戏。