パンケーキの仕分け

パンケーキの並べ替えとは、積み重ねられたパンケーキを大きさ順に並べ替える数学的な問題で、積み重ねられたパンケーキのどの点にもヘラを差し込み、その上にあるすべてのパンケーキをひっくり返すことができるという条件を満たすものです。パンケーキ数とは、与えられた数のパンケーキをひっくり返すのに必要な最小回数のことです。この形式でこの問題を最初に議論したのは、アメリカの幾何学者ジェイコブ・E・グッドマンです。^{[ 1 ]}この問題の変形版は、焦げたパンケーキに関するもので、各パンケーキには焦げた面があり、さらにすべてのパンケーキは最終的に焦げた面を下にして置かなければなりません。

すべてのソート方法では、要素のペアを比較する必要があります。従来のソート問題では、リストをソートするために必要な比較回数を最小化することが一般的な課題です。この場合、2つの要素を交換するなどの実際の操作の回数は関係ありません。一方、パンケーキソート問題では、シーケンスの特定の接頭辞の要素の反転のみが許容される操作の回数を最小化することが目的です。この場合、比較回数は関係ありません。

上記の議論では、各パンケーキが一意である、つまり、接頭辞反転を実行するシーケンスが順列であると仮定しています。しかし、「文字列」は記号が繰り返される可能性のあるシーケンスであり、この繰り返しによってソートに必要な接頭辞反転の回数が減少する可能性があります。Chitturi と Sudborough (2010) および Hurkens ら (2007) は、互換性のある文字列を最小限の接頭辞反転で別の文字列に変換する複雑さがNP 完全であることを独立して示しました。また、同じものに対する境界も示しました。Hurkens らは、バイナリ文字列と三値文字列をソートするための正確なアルゴリズムを提供しました。Chitturi ^{[ 8 ]} (2011) は、互換性のある符号付き文字列を最小限の符号付き接頭辞反転で別の文字列に変換する複雑さ (文字列の焦げたパンケーキ問題) が NP 完全であることを証明しました。

パンケーキの仕分け問題は、ジェイコブ・E・グッドマンが「ハリー・ドウェイト」（「慌ただしいウェイター」）というペンネームで最初に提起した。^{[ 9 ]}

パンケーキソートは教育ツールとしてよく見られるが、並列プロセッサネットワークのアプリケーションにも登場し、プロセッサ間の効果的なルーティングアルゴリズムを提供することができる。^{[ 10 ] [ 11 ]}

この問題は、マイクロソフトの創設者ビル・ゲイツ（ウィリアム・ゲイツ名義）がクリストス・パパディミトリウと共著した「接頭辞反転によるソートの境界」と題された、唯一よく知られた数学論文のテーマとして注目に値する。1979年に発表されたこの論文は、パンケーキソートの効率的なアルゴリズムについて述べている。^{[ 3 ]}また、フューチュラマの共同制作者デイビッド・X・コーエン（デイビッド・S・コーエン名義）がマヌエル・ブルムと共著した最も有名な論文は、焦げたパンケーキ問題に関するものだった。^{[ 12 ]}

符号付き反転ソートと反転ソートの関連問題も最近研究されている。符号付き反転ソートについては効率的な厳密アルゴリズムが見つかっているが、^{[ 13 ]}反転ソートの問題は特定の定数係数の範囲内で近似することさえ難しいことが証明されており、^{[ 14 ]}また、近似係数1.375の範囲内で多項式時間で近似できることも証明されている。^{[ 15 ]}

n-パンケーキグラフは、頂点が1からnまでのn個の記号の順列であり、辺が接頭辞反転によって推移する順列の間にあるグラフです。これはn!個の頂点を持つ正則グラフであり、次数はn - 1です。パンケーキソート問題とパンケーキグラフの直径を求める問題は同等です。^{[ 16 ]}

n次元のパンケーキグラフP _{n は、P n − 1}の n 個のコピーから再帰的に構築することができ、各コピーに集合 {1, 2, …, n} から異なる要素を接尾辞として割り当てます。

周囲長：

${\displaystyle g(P_{n})=6{\text{, if }}n>2}$。

_{P n}のγ (P _n )種数は次のとおりです。^{[ 17 ]}

${\displaystyle n!\left({\frac {n-4}{6}}\right)+1\leq \gamma (P_{n})\leq n!\left({\frac {n-3}{4}}\right)-{\frac {n}{2}}+1}$

パンケーキグラフは、対称性や再帰構造、グラフのサイズに比べて次数や直径が小さいなど、多くの興味深い特性を持っているため、並列コンピュータの相互接続ネットワークのモデルとして注目されています。^{[ 18 ] [ 19 ] [ 20 ]}パンケーキグラフを相互接続ネットワークのモデルとみなすと、グラフの直径は通信の遅延を表す尺度となります。^{[ 21 ] [ 22 ]}

パンケーキグラフはケイリーグラフ（したがって頂点推移的）であり、並列処理に特に適しています。次数と直径は対数以下であり、比較的疎です（例えばハイパーキューブと比較して）。^{[ 17 ]}

パンケーキソートアルゴリズムの例をPythonで以下に示します。このコードはバブルソートや選択ソートと似ています。

def flip ( arr , k : int ) -> None :左= 0左端< kの間:arr [ left ], arr [ k ] = arr [ k ], arr [ left ]k -= 1左+= 1def max_index ( arr , k : int ) -> int :インデックス= 0for i in range ( k ):arr [ i ] > arr [ index ]の場合:インデックス= iインデックスを返すdef pancake_sort ( arr ) -> None :n = len ( arr )n > 1 の間:maxidx = max_index ( arr , n )maxidx != n - 1 の場合:maxidx != 0 の場合:flip ( arr , maxidx )flip ( arr , n - 1 )n -= 1arr = [ 15 , 8 , 9 , 1 , 78 , 30 , 69 , 4 , 10 ]pancake_sort ( arr )print ( arr )

オンライン整数列百科事典からの数列：

• OEIS：A058986  – 最大反転回数
• OEIS：A067607  – 最大フリップ回数を必要とするスタックの数（上記参照）
• OEIS : A078941  – 「焼損」スタックの最大反転回数
• OEIS : A078942  – ソートされた「焦げた面を上にした」スタックの反転回数
• OEIS : A092113  – 上記の三角形、行ごとに読み取る

• 結び目を切る：パンケーキをひっくり返すパズル。パンケーキの問題を解くJavaアプレットと解説が含まれています。
• ダグラス・B・ウェスト著『パンケーキ問題』
• ワイススタイン、エリック W. 「パンケーキの分類」 . MathWorld .