スーパーパーミュテーション

組合せ 数学において、n個のシンボルのスーパー順列は、 n個のシンボルの各順列を部分文字列として含む文字列です。単純なスーパー順列は、単純にすべての順列を連結して構成できますが、重複が許可されているため、スーパー順列は短くなることもあります ( n = 1 の単純なケースを除く)。たとえば、 n = 2の場合、スーパー順列 1221 にはすべての可能な順列 (12 と 21) が含まれますが、短い文字列 121 には両方の順列も含まれます。

1 ≤ n ≤ 5 の場合、n個のシンボルの最小のスーパーパーミュテーションの長さは 1! + 2! + … + n ! であることが示されています( OEISのシーケンスA180632 )。最初の 4 つの最小のスーパーパーミュテーションの長さはそれぞれ 1、3、9、33 で、文字列 1、121、123121321、123412314231243121342132413214321 を形成します。ただし、n = 5 の場合、長さが 153 の最小のスーパーパーミュテーションが複数存在します。そのようなスーパーパーミュテーションの 1 つを以下に示します。同じ長さの別のスーパーパーミュテーションは、文字列の後半 (太字の2の後) の 4 と 5 をすべて入れ替えることで取得できます。^[1]

1234512341523412534123541231452314253142351423154231245312435124315243125431 2 1345213425134215342135421324513241532413524132541321453214352143251432154321

n > 5の場合、最小の超順列はまだ証明されておらず、それを見つけるパターンもまだありませんが、それらの下限と上限は見つかりました。

順序の超順列を作成するための最も一般的なアルゴリズムの 1 つは、再帰アルゴリズムです。まず、順序の超順列は、超順列に現れた順序で個々の順列に分割されます。次に、これらの順列のそれぞれを、そのコピーの隣に配置し、 2 つのコピーの間にn番目のシンボルを追加します。最後に、結果として得られた各構造を互いに隣り合わせに配置し、隣接するすべての同一シンボルを結合します。^[2]${\displaystyle n}$${\displaystyle n-1}$

たとえば、2 つのシンボルを持つ順列から 3 次超順列を作成できます。超順列 121 から始めて、順列 12 と 21 に分割し、順列をコピーして 12312 と 21321 として配置します。これらを一緒に配置して 1231221321 を作成し、中央の隣接する同一の 2 を結合して 123121321 を作成します。これは確かに 3 次超順列です。このアルゴリズムは、nが 5 以下の場合はすべて最短の超順列になりますが、 n がそれを超えると、最短よりも長くなります。 ^[2]

スーパー順列を見つける別の方法は、各順列が頂点で、すべての順列が辺で接続されているグラフを作成することです。各辺には重みが関連付けられています。重みは、1 つの順列の末尾に何文字追加できるか（同じ数の文字を先頭から削除する）によって計算され、他の順列が生成されます。^[2]たとえば、123 から 312 への辺の重みは 2 です。これは、123 + 12 = 12312 = 312 であるためです。作成されたグラフを通るハミルトン パスはすべてスーパー順列であり、最小の重みを持つパスを見つける問題は、巡回セールスマン問題の一種になります。長さより小さいスーパー順列の最初の例は、ロビン ヒューストンによるこの方法のコンピューター検索を使用して見つかりました。 ${\displaystyle 1!+2!+\ldots +n!}$

2011年9月、4chanの科学と数学（「 /sci/」）掲示板に匿名の投稿者が、 n個のシンボル（n ≥ 2）の最小の超順列の長さは少なくともn ! + ( n −1)! + ( n −2)! + n − 3であることを証明した。 ^[3]日本のアニメシリーズ「涼宮ハルヒの憂鬱」 、特にそれがもともと非線形の物語として放送されていたという事実に関連して、この問題は画像掲示板で「ハルヒ問題」として提示された。^[4]シリーズの最初のシーズンの14のエピソードをあらゆる可能な順序で見たい場合、見なければならないエピソードの最短の文字列はどれでしょうか？^[5]この下限の証明は、数学者でコンピューター科学者のロビン・ヒューストンがそれについてツイートした後、2018年10月に一般の人々の関心を引くことになった。^[3] 2018年10月25日、ロビン・ヒューストン、ジェイ・パントン、ヴィンス・ヴァッターは、この証明の改良版をオンライン整数列百科事典（OEIS）に掲載した。^{[5] [6]}この証明の公開版は、「匿名の4chan投稿者」によるもので、エンゲンとヴァッター（2021）に掲載されている。^[7]

特に「ハルヒ問題」（14個のシンボルの場合）の場合、現在の下限と上限はそれぞれ93,884,313,611と93,924,230,411です。^[3]これは、シリーズをあらゆる順序で視聴するには約430万年かかることを意味します。^[8]

2018年10月20日、対称群のケーリーグラフを通るハミルトン経路を構築するためのアーロン・ウィリアムズの構築を応用して、^[9] SF作家で数学者のグレッグ・イーガンは、長さn ! + ( n −1)! + ( n −2)! + ( n −3)! + n − 3の超順列を生成するアルゴリズムを考案しました。 ^[2] 2018年まで、これらはn ≥ 7で知られている最小の超順列でした。しかし、2019年2月1日、ボグダン・コアンダは、n = 7の長さ5907、つまり( n ! + ( n −1)! + ( n −2)! + ( n −3)! + n − 3) − 1の超順列を発見したと発表しました。これは新記録でした。^[2] 2019年2月27日、ロビン・ヒューストンのアイデアを使用して、イーガンは長さ5906のn = 7のスーパーパーミュテーションを作成しました。 ^[2] n > 7の値に対しても同様の短いスーパーパーミュテーションが存在するかどうかは未解決の問題です。n = 7の現在の最良の下限（上記のセクションを参照）は依然として5884です。

• スーパーパターン、 n個のシンボルの各順列を順列パターンとして含む順列
• ド・ブリュイン列、巡回列に関する同様の問題

• アシュロック、ダニエル A.; ティロットソン、ジェネット (1993)、「小さなスーパーパーミュテーションと極小の単射スーパーストリングの構築」、Congressus Numerantium、93 :91–98、Zbl  0801.05004
• 匿名 4chan ポスター、Houston, Robin、Pantone, Jay、Vatter, Vince (2018 年 10 月 25 日)。「最短スーパーパターンの長さの下限値」(PDF)。オンライン整数シーケンス百科事典。

• 最小の超順列問題 - ナサニエル・ジョンストンのブログ
• グライム、ジェームズ。「Superpermutations - Numberphile」（ビデオ）。YouTube 。ブレイディ・ハラン。 2018年2月1日閲覧。
• /sci/ の元の 4chan 投稿。warosu.org にアーカイブされています。
• 4chanの投稿に注目を呼んだロビン・ヒューストンのツイート
• Quanta Magazineの短い超順列を見つける問題に関する記事