<ruby><rb data-id="template-ruby"><span lang="zh">凉宫春日问题</span><span class="template-ruby-hidden">（</span></rb><rt style="font-size:0.75em"><span lang="zh">最小超排列问题</span></rt><span class="template-ruby-hidden">）</span></ruby>
| |
| 基本资料 | |
| 用语名称 | 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在推特上公开了上述文献调研结果时才引起了人们的兴趣，他很快与另外两位数学家一起整理规范了该乡民张贴的证明过程与结果，以预印本论文形式发表于同年10月25日，文中匿名乡民被署记为Anonymous 4chan Poster，位列第一作者。[2]
根据该算法，当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版凉宫全部可能的排列方法，也不会看超过九百三十九亿二千四百二十三万零四百一十一集。
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| |||||||||||||||||||||||||||||||||
注释与引用
- ↑ /sci/ : The Haruhi Problem
- ↑ 2.0 2.1 A lower bound on the length of the shortest superpattern Anonymous 4chan Poster, Robin Houston, Jay Pantone,Vince Vatter
- ↑ OEIS：A180632
- ↑ . "Permutations Thread III" 4chan：Anonymous(2011年9月17日)
- ↑ Greg Egan：Superpermutations