2023年政策修订增补工作正在进行中，欢迎参与！
  • Moegirl.ICU：萌娘百科流亡社群 581077156（QQ），欢迎对萌娘百科运营感到失望的编辑者加入！
  • Moegirl.ICU：账号认领正在试运行，有意者请参照账号认领流程。

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

萌娘百科，万物皆可萌的百科全书！转载请标注来源页面的网页链接，并声明引自萌娘百科。内容不可商用。
跳转到导航 跳转到搜索

Flag of MOEA.jpg
本条目为国际萌能机构伪媛会正在进行或监控的萌能项目，以及机构所认可的原创研究成果。
Zozlogo.jpg
我对普通的条目没有兴趣！
假如你们当中有人能把这个世界变得更热闹的话，尽管来协助编辑本条目吧！
编辑前请阅读Wiki入门或条目编辑规范，并查找相关资料。完毕！
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在推特上公开了上述文献调研结果时才引起了人们的兴趣，他很快与另外两位数学家一起整理规范了该乡民张贴的证明过程与结果，以预印本论文形式发表于同年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版凉宫全部可能的排列方法，也不会看超过九百三十九亿二千四百二十三万零四百一十一集。


 
查 · 论 · 编
Zozlogo.jpg凉宫春日系列（涼宮ハルヒシリーズ）
登场人物
SOS团
SOS团关系人
同班同学
谷口 • 国木田 • 朝仓凉子（宇宙人） • T（推理研究社社员兼鹤屋学姐密友）
其他班级
鹤屋学姐（有钱人、SOS团名誉顾问） • 喜绿江美里（宇宙人） • 电研部部长（SOS团首席受害人）
小学生
“机关”相关
宠物
三味线（喵星人）
其他
佐佐木集团(伪SOS团)
佐佐木（神？） • 周防九曜（宇宙人） • 橘京子（超能力者） • 藤原（未来人）
县立北高校1年5班其他学生
（按座位顺序）
女生
西岛唯 • 大野木菜菜夏 • 日向咲叶 • 成崎彩乃 • 剑持琴音 • 濑能佳织 • 柳本堇 • 高远幸菜 • 佐伯瑞穗 • 叶山玲子 • 由良奏绘 • 阪中佳实 • 铃木美春
男生
垣之内翔也 • 花濑樱太 • 荒川剑之介 • 吉崎宏一 • 松代圭吾 • 中岛昭裕 • 山根幸广 • 后藤恭介 • 植松雅树 • 丰原升 • 手岛一平 • 榊大地
ENOZ乐队
游戏版原创角色
相关音乐
动画音乐
凉宫春日的忧郁
冒険でしょでしょ?（OP1） • Super Driver（OP2） • ハレ晴レユカイ（ED1） • 止マレ!（ED2）
恋のミクル伝説（IN） • God knows...（IN） • Lost my music（IN）
凉宫春日的消失
小凉宫春日的忧郁
いままでのあらすじ（OP） • あとがきのようなもの（ED） • Paradise Lost（IN） • 涼宮ハルヒちゃんの憂鬱ギャルゲー版
小长门有希的消失
游戏音乐
凉宫春日的约定
凉宫春日的困惑
凉宫春日的激动
凉宫春日的并联
凉宫春日的串联
凉宫春日的追忆
小凉宫春日的麻将
角色歌曲
凉宫春日的忧郁06
パラレル Days（凉宫春日CS） • SOS ならだいじょーぶ（凉宫春日CS） • 雪、無音、窓辺にて。（长门有希CS） • SELECT?（长门有希CS） • 見つけて Happy Life（朝比奈实玖瑠CS） • 時のパズル（朝比奈实玖瑠CS） • 青春いいじゃないかっ（鹤屋CS） • めがっさ好奇心（鹤屋CS） • 小指でぎゅっ！（朝仓凉子CS） • COOL EDITION（朝仓凉子CS） • 妹わすれちゃおしおきよ（虚妹CS） • fixed mind（喜绿江美里CS） • まっがれ↓スペクタクル（古泉一树CS） • 倦怠ライフ-リターンズ！（阿虚CS）
凉宫春日的忧郁09
Punkish regular（凉宫春日CS） • その日空はきっと青い（凉宫春日CS） • under "Mebius"（长门有希CS） • 通過地点のMUSICA（长门有希CS） • えっと…リターンズしてリベンジ!（朝比奈实玖瑠CS） • ヘンですコワイですっ（朝比奈实玖瑠CS） • 「つまらない話ですよ」と僕は言う（古泉一树CS） • ただの秘密（古泉一树CS） • ホモ・サピエンス・ラプソディ（阿虚CS） • だがそれだけじゃない（阿虚CS） • 祭って祭って！いらっしゃい（鹤屋CS） • お騒がせのジ・エンド（鹤屋CS） • 人生の主役コール（谷口CS） • 友達としてはソレが（谷口CS）
小长门有希的消失
窓辺の予感（长门有希CS） • 探していた風景（长门有希CS） • しあわせは日常のなかで（朝仓凉子CS） • LOVE EDITION（朝仓凉子CS） • 恋はミらいからクル?（朝比奈实玖瑠CS） • 太陽とデイジー（朝比奈实玖瑠CS） • 愛の門番EXTRA（鹤屋CS） • 福が来たりて風が吹く（鹤屋CS） • Dreamerという冒険者（凉宫春日CS） • 錯覚Loving’ you?（凉宫春日CS）
其他音乐
Imaginary ENOZ
featuring HARUHI
Drama
创作相关
系列作品
小说原作
动画
漫画
游戏
作品相关
朝比奈实玖瑠的冒险（本篇中的剧中剧） • 漫无止境的八月（本篇中的知名部分） • 射手座之日（本篇中的虚构游戏）
本篇创作人员和公司
谷川流（小说原作） • 伊东杂音（原作插画） • 京都动画（动画制作） • 石原立也&武本康弘（动画监督） • 山本宽（动画系列演出等） • 神前晓（动画音乐） • 畑亚贵（动画主题歌作词等） • 水野诚（漫画版作画） • 都贺野岳（漫画版作画）
番外创作人员和公司
Puyo（《有希酱》《春日酱》漫画） • Eretto（《鹤屋酱》漫画） • SATELIGHT（《有希酱》动画制作） • 京都动画（《春日酱》《鹤屋酱》动画制作）
梗相关
粉丝文化
凉宫春日的性转换
音乐
学术
 
查 · 论 · 编
数学相关条目
数学萌化
萌化数学概念
萌化数学定理
萌化数学问题
ACGN中的数学要素
数学要素总览列表
数学相关音乐
数学相关作品
数学相关用语
数学相关角色
数学相关萌属性

注释与引用

  1. ↑ /sci/ : The Haruhi Problem
  2. ↑ 2.0 2.1 A lower bound on the length of the shortest superpattern Anonymous 4chan Poster, Robin Houston, Jay Pantone,Vince Vatter
  3. ↑ OEIS：A180632
  4. ↑ . "Permutations Thread III" 4chan：Anonymous(2011年9月17日)
  5. ↑ Greg Egan：Superpermutations
取自“https://moegirl.icu/index.php?title=凉宫春日问题&oldid=7320209”