コンテンツにスキップ

超置換

出典: フリー百科事典『ウィキペディア（Wikipedia）』

組合せ数学における n 記号の超置換（ちょうちかん、英: superpermutation）とは、n個の記号の全ての置換を部分文字列（substring）として含む文字列。最小の超置換を求める問題は2025年時点で未解決である。

1≤n≤5に対しては、最小の n 記号の超置換の長さは 1!+2!+⋯+n! に等しい。つまり、順に 1,3,9,33,153 （オンライン整数列大辞典の数列 A180632）である。

最小の超置換の具体的な例としては 1,121,123121321,123412314231243121342132413214321 及び以下のものが挙げられる :

123451234152341253412354123145231425314235142315423124531243
512431524312543121345213425134215342135421324513241532413524
132541321453214352143251432154321

n≥6 においても同様の式で長さを求められると予想されていたが、それは成り立たないことが判明している。n=6 の場合、 6!+5!+4!+3!+2!+1!=873 よりも短い、長さが 872 のものがRobin Houstonによって発見されたからである。[1]

なお、n=7 および n=8 の場合もそれぞれ長さ5908[2]、46205[3]のものが確認されており、この数値が最小かどうかは未だ証明されていない。今もさらに短いものを探す試みは継続しており、n=7 においては、2019年2月1日には長さ5907のものが[4]、2019年2月27日には長さ5906[5]のものが次々と発見された。

最小超置換の長さ

[編集]

最小超置換の正確な長さは未だ求められていないが、答えの範囲は次のように絞り込まれている。

下界

[編集]

2011年9月、4chanの匿名投稿者が n 記号の超置換 (n≥2) の長さは少なくとも n!+(n−1)!+(n−2)!+n−3 以上であることを証明した[6]。この証明は4chanにおいて、アニメシリーズ『涼宮ハルヒの憂鬱』第1期全14話は2006年の放送時は物語の時系列とは異なる順序で放映されたため、エピソードをどの順序で観るのがよいのか、という疑問がきっかけになったことから、「ハルヒ問題」とも呼ばれる。[7]この証明が大衆の関心を引いたのは、2018年10月に数学者兼計算機科学者のロビン・ヒューストンがツイートして以降である[8][9]。2018年10月25日、ロビン・ヒューストン、ジェイ・パントン、ヴィンス・ヴァッターはこの証明をより洗練させたものをOEISに投稿した[10]。

上界

[編集]

2018年10月20日、グレッグ・イーガンは、アーロン・ウィリアムズが対称群のケイリーグラフのハミルトン路を構成するのに用いた方法[11]を適用することで、長さ n!+(n−1)!+(n−2)!+(n−3)!+n−3 の超置換を生成するアルゴリズムを開発した[12]。2018年の時点で、これらは n≥7 に対しては知られている中で最小の超置換である。2019年には、n=7 に対して、(n!+(n−1)!+(n−2)!+(n−3)!+n−3)−1にあたる5906 がよりよい上界になった。

関連項目

[編集]

注釈

[編集]
  • Ashlock, Daniel A.; Tillotson, Jenett (1993), “Construction of small superpermutations and minimal injective superstrings”, Congressus Numerantium 93: 91–98, Zbl 0801.05004 
  • Johnston, Nathaniel (July 28, 2013), “Non-uniqueness of minimal superpermutations”, Discrete Mathematics 313 (14): 1553–1557, arXiv:1303.4150, doi:10.1016/j.disc.2013.03.024, Zbl 1368.05004, http://www.njohnston.ca/publications/non-uniqueness-of-minimal-superpermutations/ 2014年3月16日閲覧。 
  • Houston, Robin (21 August 2014), “Tackling the Minimal Superpermutation Problem”, arXiv:1408.5108 [math.CO]

参考文献

[編集]
  1. ↑ Robin Houston (2014-08-22). “Tackling the Minimal Superpermutation Problem”. 不明.
  2. ↑ “n = 7, with 5908 digits”. 2025年4月2日閲覧。
  3. ↑ “n = 8, with 46 205 digits”. 2025年4月2日閲覧。
  4. ↑ “Superpermutation for n=7 of length 5907”. 2025年4月2日閲覧。
  5. ↑ “n = 7, with 5906 digits”. 2025年4月2日閲覧。
  6. ↑ Anonymous (2011年9月17日). “Permutations Thread III”. Warosu, a 4chan archive. 2018年10月27日閲覧。
  7. ↑ “4chan Just Solved A Decades-Old Mathematical Mystery”. 2025年5月20日閲覧。
  8. ↑ Griggs, Mary Beth. “An anonymous 4chan post could help solve a 25-year-old math mystery”. The Verge. 2018年10月24日閲覧。
  9. ↑ Houston, Robin. “A curious situation. The best known lower bound... (1054637891085918209)” (英語). Twitter. 2018年10月27日閲覧。
  10. ↑ Anonymous 4chan poster (2018年10月25日). “A lower bound on the length of the shortest superpattern”. OEIS. 2018年10月27日閲覧。
  11. ↑ Aaron, Williams. “Hamiltonicity of the Cayley Digraph on the Symmetric Group Generated by σ = (1 2 ... n) and τ = (1 2)”. arXiv:1307.2549v3.{{cite arXiv}}: CS1メンテナンス: classが不足 (カテゴリ)
  12. ↑ Egan, Greg (2018年10月20日). “Superpermutations”. 2018年10月27日閲覧。

外部リンク

[編集]
「https://ja.wikipedia.org/w/index.php?title=超置換&oldid=110896445」から取得