• 你好~!欢迎来到萌娘百科!如果您是第一次来到这里,点这里加入萌娘百科!
  • 欢迎具有翻译能力的同学~有意者请点→Category:需要翻译的条目
  • 如果您在萌娘百科上发现某些内容错误/空缺,请勇于修正/添加!编辑萌娘百科其实很容易!
  • 觉得萌娘百科有趣的话,请推荐给朋友哦~
  • 萌娘百科群119170500欢迎加入,加入时请写明【萌娘百科+自己的ID】~
  • 萌娘百科Discord群组已经建立,请点此加入!

凉宫春日问题最小超排列问题

萌娘百科,万物皆可萌的百科全书!
跳转至: 导航搜索

Flag of MOEA.jpg
本条目为国际萌能机构伪媛会正在进行或监控的萌能项目,以及机构所认可的原创研究成果。
The Haruhi Problem.jpg
基本资料
用语名称 The Haruhi Problem
ハルヒ問題;
究極のハルヒマラソン問題

春日问题;凉宫春日问题)
其他表述 The Minimal Superpermutation Problem
最小超置換問題
最小超排列问题)
相关条目 凉宫春日的忧郁乱序播放凉宫春日

凉宫春日问题(The Haruhi Problem;春日问题;ハルヒ問題[1][2],数学界通称最小超排列问题(The Minimal Superpermutation Problem;最小超置換問題[3]是一个组合计数难题,原型(如图)表述为:


What is the least number of Haruhi episodes that you would have to watch in order to see the original 14 episodes in every order possible?
如想以所有可能的顺序看完凉宫春日初版14话动画则最少要看多少话?

推广后的一种抽象数学表述为:

What is the minimum length of a string of symbols that contains every permutation of n symbols
包含n种字符全部排列的字符串其最小长度为何?

ACG背景

《凉宫春日的忧郁》共拍摄了2006与2009两个版本的TV动画,其中初版(06版)首播为乱序播放,共14话。其TV播放顺序与故事的时间轴顺序,以及后来的DVD版收录顺序均不相同。

话数 日文标题 中文标题 首播时间
播放顺序 故事顺序 DVD收录顺序
01 11 01 朝比奈ミクルの冒険 Episode00 朝比奈实玖瑠的冒险 Episode00 2006年4月2日
02 01 02 涼宮ハルヒの憂鬱I 凉宫春日的忧郁 Ⅰ 2006年4月9日
03 02 03 涼宮ハルヒの憂鬱II 凉宫春日的忧郁 Ⅱ 2006年4月16日
05 03 04 涼宮ハルヒの憂鬱III 凉宫春日的忧郁 Ⅲ 2006年4月30日
10 04 05 涼宮ハルヒの憂鬱IV 凉宫春日的忧郁 Ⅳ 2006年6月4日
13 05 06 涼宮ハルヒの憂鬱V 凉宫春日的忧郁 Ⅴ 2006年6月25日
14 06 07 涼宮ハルヒの憂鬱VI 凉宫春日的忧郁 Ⅵ 2006年7月2日
04 07 08 涼宮ハルヒの退屈 凉宫春日的烦闷 2006年4月23日
07 08 09 ミステリックサイン 神秘信号 2006年5月14日
06 09 10 孤島症候群(前編) 孤岛症候群(前篇) 2006年5月7日
08 10 11 孤島症候群(後編) 孤岛症候群(后篇) 2006年5月21日
12 12 12 ライブアライブ Live Alive 2006年6月18日
11 13 13 射手座の日 射手座之日 2006年6月11日
09 14 14 サムデイ イン ザ レイン Someday in the Rain 2006年5月28日


数学背景

定义n个字符的超排列(superpermutation)为其子串包含所有n个字符的排列的字符串,则春日问题等价于寻找n个字符最小超排列的长度。

例如,当1 ≤ n ≤ 5时,最小排列的长度为 1! + 2! + … + n! ,对应的超排列为1, 121, 123121321, 123412314231243121342132413214321, 以及

123451234152341253412354123145231425314235142315423124531243
512431524312543121345213425134215342135421324513241532413524
132541321453214352143251432154321


2011年,在著名网络屎尿屁论坛4chan上,用户ニア爱 !pQsULI4sXc发布了包含春日问题原型的改图,意外地引发了严肃讨论。一位匿名用户肥肥随后在论坛推导出了一个n个字符的超排列所至少具有的长度为:

n! + (n-1)! + (n-2)! + n - 3  (n≥2)[4]

这个结果是目前最优(长)的超排列长度下界。

遗憾的是,乡民的这一成果在当时并未引起数学界的足够重视。直到2018年,经数学家Robin Houston在推特上公开了这一文献调研结果,才引起了人们的兴趣。

根据匿名乡民的算法,当n=14时,目前下界的最优解为93,884,313,611

也就是说宅宅们现在至少需要马拉松式地连续看九百三十八亿八千四百三十一万三千六百一十一集06版凉宫,才有可能欣赏到全部可能的排列方法。


另一方面,目前最优(短)的最小超排列长度上界:

n! + (n-1)! + (n-2)! + (n-3)!+n - 3 (n≥7)[5]

则是由数学家、科幻作家Greg Egan在2018年10月提出的。当n=14时,上界为93,924,230,411

也就是说宅宅们马拉松式地以最短方法连续欣赏完06版凉宫全部可能的排列方法,也不会看超过九百三十九亿二千四百二十三万零四百一十一集。


注释与引用

  1. /sci/ : The Haruhi Problem
  2. A lower bound on the length of the shortest superpattern Anonymous 4chan Poster, Robin Houston, Jay Pantone,Vince Vatter:引用Ref1:/sci/表述
  3. OEIS:A180632
  4. . "Permutations Thread III" 4chan:Anonymous(2011年9月17日)
  5. Greg Egan:Superpermutations