煎餅排序

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

## 煎餅問題

### 最初的煎餅問題

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

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

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

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

### 焦煎餅問題

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

## 字串中的煎餅問題

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

## 歷史

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

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

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

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

## 煎餅圖

<image>

<image>

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

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

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

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

Pn的虧格γ(Pn)為：

$$n!\left( \frac{n-4}{6} \right)+1 \le \gamma(P_n) \le n!\left( \frac{n-3}{4} \right)-\frac{n}{2}+1$$

煎餅圖有許多有趣的性質，例如對稱性和上文所述的遞歸結構。另外，它是凱萊圖，因此也是頂點傳遞圖。隨著維度的增加，煎餅圖的度數和直徑都以低於對數的速度增長，因此它比超方形圖等圖更為稠密圖。人們對其在並行計算的互連網路模型的應用非常關注。如果把煎餅圖視為互連網路的模型，它的直徑大小可以衡量通信延遲高低。

## 相關整數序列

高度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

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

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

## 外部連結

- Cut-the-Knot上的翻煎餅謎題，用Java實現的煎餅問題程序，以及一些討論。
- 道格拉斯·韋斯特講述的煎餅問題
- 一部小動畫，演示了細菌電腦如何解決焦煎餅問題。