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」