煎餅排序

煎餅排序（英語：Pancake sorting）指的是將大小不同的一疊煎餅按大小排序的數學問題，其中抹刀（英語：spatula）每次只能從任意位置鏟起上方全部煎餅並翻面。「煎餅數」（英語：pancake number）是指給定煎餅的張數時，最壞情況下需要的最少翻面次數。這個問題最早由美國幾何學家雅各布·E·古德曼提出。^[1]它屬於排序問題的變種。煎餅排序的目標和傳統排序演算法最小化比較次數不同，因為它每次操作只允許反轉序列的字首（英語：prefix (computer science)），所以需要最小化反轉字首次數。焦煎餅排序是煎餅排序的變種問題，每張煎餅都有一面是烤焦的，最終除了按照大小排序以外還要讓所有焦面向下。

一次範例操作。上方是用煎餅鏟子將頂上三張煎餅翻面，翻完以後變為下方所示的狀態。在焦煎餅問題中，如果原來三張餅的焦面朝下，則翻完之後變為焦面朝上

煎餅問題

最初的煎餅問題

對於任意一疊n張煎餅，人們已經證明最小翻轉次數在15/14n到18/11n之間（約為1.07n到1.64n之間），但精確值仍未知^[2]。

最簡單的演算法在最壞情況下需要2n − 3次翻轉。這種演算法是選擇排序的變體，每輪用一次翻轉把未排序的煎餅中最大者翻到頂上，再用一次翻轉把它翻到最終所在處（目前未排序煎餅和已排序煎餅的交界處），然後對剩餘未排序煎餅重複此過程。剩下兩個煎餅時只需一次翻轉即完成排序。

1979年比爾·蓋茲和赫里斯托斯·帕帕季米特里烏給出了一個上界5n+5/3^[3]。三十年後德克薩斯州大學達拉斯分校薩薄若（Sudborough）教授領導的一組研究者將這個上界改進為18/11n^[4][5]。

2011年，勞倫特·比爾托（Laurent Bulteau）、紀堯姆·佛丁（Guillaume Fertin）和伊雷娜·魯蘇（Irena Rusu）證明了給定一疊煎餅的長度分布，找到最短解法是NP困難的，最終解決了這個已提出三十餘年的問題。^[6]

焦煎餅問題

焦煎餅問題（英語：Burnt pancake problem）是煎餅問題的一種變體，其中每個煎餅有一面是焦的，排序後必須使所有煎餅焦的一面朝下。這是一類帶符號的排列問題（英語：signed permutation），如果某個煎餅焦的一面朝上，就在排列中給它加一個符號，最後結果必須不含符號。2008年，一組本科生對大腸桿菌程式設計，構造細菌電腦讓其翻轉類似焦煎餅的DNA序列，解決了一個簡單的焦煎餅問題。DNA具有方向性（5'端和3'端）和順序（啟動子和編碼區）。雖然細菌對DNA翻轉的處理能力較弱，但單次培養中為數眾多的細菌提供了龐大的平行計算平台。當細菌帶有抗生素抗藥性時，DNA序列的排序問題即告解決。^[7]

字串中的煎餅問題

如果將煎餅疊視為一個字串，每次翻轉相當於取一段字首並將其反轉，這是一個置換操作。不過，前述討論假定每個煎餅都是不同的，但是字串可以包含相同字元，因此字首反轉所需次數可能會減少。赫肯斯（Hurkens）等人在2007年構造了二元和三元字串字首反轉排序的多項式時間精確演算法^[8]，並證明了用最少的字首反轉次數將一個二元字串轉換為另一個二元字串是NP困難的。池圖瑞（Chitturi）等人^[9]於2010年將上述結論推廣到了一般字串，證明了它是NP完全的，並給出了最少次數的上下界。池圖瑞在2011年證明了帶符號的字串字首反轉排序（即字串中的焦煎餅問題）也是NP完全的^[10]。

歷史 

煎餅排序問題最初由雅可比·古德曼（英語：Jacob E. Goodman）提出，他當時用了假名「哈利·德威特」（原文「Harry Dweighter」，音近「harried waiter」，即「忙亂的侍應」）。^[11]

煎餅問題更多地在教育中見到，但也會在並列處理網路中用到，它的解答對應著處理器之間高效的最短路演算法。^[12][13]這個問題也在計算生物學中有所應用^[6]。

微軟公司創立者比爾·蓋茲就這個問題在1979年發表過一篇題為《字首逆轉排序的邊界問題》（英語：Bounds for Sorting by Prefix Reversal）的論文，這是他唯一廣為人知的數學論文。在這篇論文中蓋茲描述了一種高效的煎餅排序演算法。^[3]另外，《飛出個未來》的主創之一大衛·科恩（英語：David X. Cohen）研究了焦煎餅問題。^[14]他們兩位的合作者分別是赫里斯托斯·帕帕季米特里烏（當時在哈佛大學任職，目前在哥倫比亞大學）與曼紐爾·布盧姆（當時在加利福尼亞大學柏克萊分校任職，目前在卡內基·梅隆大學）。

之後，相關的字串子串反轉排序問題也得到了研究。不過，帶符號的子串反轉排序問題有平方時間的精確演算法^[15]，但（不帶符號的）子串反轉問題不存在多項式時間的精確演算法，其多項式時間近似演算法的近似因子下界為1.0008，上界為1.5^[16]，後來找到了近似因子為1.375的多項式時間近似演算法^[17]。

煎餅圖

煎餅圖P₃

煎餅圖P₄可以用4個P₃遞迴地構造：給每個子圖編號1、2、3、4，編號為i的子圖每個頂點對應的排列為1－4除去i的全排列，末尾加上i

主條目：煎餅圖（英語：Pancake graph）

n-煎餅圖的頂點用1到n的全排列編號，兩個頂點之間有邊若且唯若兩個頂點對應的排列可以由字首反轉得到。它是n!個頂點的正則圖，度數為n−1。煎餅排序問題等價於求取煎餅圖的直徑。^[18]

n-煎餅圖記為P_n，可以使用n個P_n−1遞迴地構建：給每個子煎餅圖分別編號1、2、……、n，編號為i的子圖每個頂點對應的排列為1－n這n個數除去i的全排列，末尾加上i。

三階及以上的煎餅圖圍長恆為6：

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

P_n的虧格γ(P_n)為：^[19]

${\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}$

煎餅圖有許多有趣的性質，例如對稱性和上文所述的遞迴結構。另外，它是凱萊圖，因此也是頂點遞移圖（英語：Vertex-transitive graph）。隨著維度的增加，煎餅圖的度數和直徑都以低於對數的速度增長，因此它比超方形圖（英語：Hypercube graph）等圖更為稀疏（英語：Dense graph）。^[19]人們對其在平行計算的互連網路模型的應用非常關注。^[20][21][22]如果把煎餅圖視為互連網路的模型，它的直徑大小可以衡量通訊延遲高低^[23][24]。

相關整數序列 

給定一疊n個煎餅，有多少種長度排列可以在翻k次以內排好序

高度 n	k
	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
1	1
2	1	1
3	1	2	2	1
4	1	3	6	11	3
5	1	4	12	35	48	20
6	1	5	20	79	199	281	133	2
7	1	6	30	149	543	1357	1903	1016	35
8	1	7	42	251	1191	4281	10561	15011	8520	455
9	1	8	56	391	2278	10666	38015	93585	132697	79379	5804
10	1	9	72	575	3963	22825	106461	377863	919365	1309756	814678	73232
11	1	10	90	809	6429	43891	252737	1174766	4126515	9981073	14250471	9123648	956354	6
12	1	11	110	1099	9883	77937	533397	3064788	14141929	49337252	118420043	169332213	111050066	13032704	167
13	1	12	132	1451	14556	130096	1030505	7046318	40309555	184992275	639783475	1525125357	2183056566	1458653648	186874852	2001

在整數數列線上大全中，有一些序列與煎餅排序有關^[10]：

• A058986 – 最壞情況下需要翻的次數
• A067607 – 有多少種煎餅長度排列是最壞情況（即上表每行最後一個數）
• A078941 – 焦煎餅問題中最壞情況下需要翻的次數
• A078942 – 有多少種焦煎餅長度排列是最壞情況
• A092113 – 即將上表每一行連接起來