煎餅排序

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

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

煎餅問題[編輯]

最初的煎餅問題[編輯]

對於任意一疊 $n$ 張煎餅，人們已經證明最小翻轉次數在 $.mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output .sfrac.tion,.mw-parser-output .sfrac .tion{display:inline-block;vertical-align:-0.5em;font-size:85%;text-align:center}.mw-parser-output .sfrac .num,.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0 0.1em}.mw-parser-output .sfrac .den{border-top:1px solid}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}15/14n$ 到 $18 / 11 n$ 之間（約為1.07n到1.64n之間），但精確值仍未知^[2]。

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

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

煎餅圖[編輯]

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

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

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

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

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

$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]。

參考文獻 [編輯]

^ Simon Singh. Flipping pancakes with mathematics. The Guardian. 2013-11-14 [2018-04-07]. （原始內容存檔於2017-07-30）.
^ Fertin, G.; Labarre, A.; Rusu, I.; Tannier, E.; Vialette, S. Combinatorics of Genome Rearrangements. The MIT Press. 2009. ISBN 9780262062824.
^ ^3.0 ^3.1 Gates, W.; Papadimitriou, C. Bounds for Sorting by Prefix Reversal (PDF). Discrete Mathematics. 1979, 27: 47–57 [2018-04-06]. doi:10.1016/0012-365X(79)90068-2. （原始內容 (PDF)存檔於2007-06-10）.
^ Team Bests Young Bill Gates With Improved Answer to So-Called Pancake Problem in Mathematics. University of Texas at Dallas News Center. 2008-09-17 [2018-04-07]. （原始內容存檔於2012-04-05）. A team of UT Dallas computer science students and their faculty adviser have improved upon a longstanding solution to a mathematical conundrum known as the pancake problem. The previous best solution, which stood for almost 30 years, was devised by Bill Gates and one of his Harvard instructors, Christos Papadimitriou, several years before Microsoft was established.
^ Chitturi, B.; Fahle, W.; Meng, Z.; Morales, L.; Shields, C. O.; Sudborough, I. H.; Voit, W. An (18/11)n upper bound for sorting by prefix reversals. Theoretical Computer Science. Graphs, Games and Computation: Dedicated to Professor Burkhard Monien on the Occasion of his 65th Birthday. 2009-08-31, 410 (36): 3372–3390 [2018-04-06]. doi:10.1016/j.tcs.2008.04.045. （原始內容存檔於2020-11-11）.
^ ^6.0 ^6.1 Bulteau, Laurent; Fertin, Guillaume; Rusu, Irena. Pancake Flipping Is Hard. Journal of Computer and System Sciences: 1556–1574. arXiv:1111.0434v1 . doi:10.1016/j.jcss.2015.02.003.
^ Haynes, Karmella A; Broderick, Marian L; Brown, Adam D; Butner, Trevor L; Dickson, James O; Harden, W Lance; Heard, Lane H; Jessen, Eric L; Malloy, Kelly J; Ogden, Brad J; Rosemond, Sabriya; Simpson, Samantha; Zwack, Erin; Campbell, A Malcolm; Eckdahl, Todd T; Heyer, Laurie J; Poet, Jeffrey L. Engineering bacteria to solve the Burnt Pancake Problem. Journal of Biological Engineering. 2008, 2: 8. PMC 2427008 . PMID 18492232. doi:10.1186/1754-1611-2-8.
^ Hurkens, Cor; van Iersel, Leo; Keijsper, Judith; Kelk, Steven; Stougie, Leen; Tromp, John. Prefix Reversals on Binary and Ternary Strings. SIAM Journal on Discrete Mathematics. 2007-01, 21 (3): 592–611. arXiv:math/0602456 . doi:10.1137/060664252.
^ B Chitturi, IH Sudborough. Prefix Reversals on Strings (PDF). Proceedings of the International Conference on Bioinformatics & Computational Biology. 2010, 2: 591–598. （原始內容存檔 (PDF)於2018-04-07）.
^ ^10.0 ^10.1 A NOTE ON COMPLEXITY OF GENETIC MUTATIONS. Discrete Mathematics, Algorithms and Applications. 2011, 03 (03): 269–287. doi:10.1142/S1793830911001206.
^ Dweighter, Harry, Elementary Problem E2569, Amer. Math. Monthly, 1975, 82: 1010, doi:10.2307/2318260
^ Gargano, L.; Vaccaro, U.; Vozella, A. Fault tolerant routing in the star and pancake interconnection networks. Information Processing Letters. 1993, 45 (6): 315–320. MR 1216942. doi:10.1016/0020-0190(93)90043-9. .
^ Kaneko, K.; Peng, S. Disjoint paths routing in pancake graphs. Proceedings of Seventh International Conference on Parallel and Distributed Computing, Applications and Technologies, 2006 (PDCAT '06). 2006: 254–259. ISBN 0-7695-2736-1. doi:10.1109/PDCAT.2006.56. .
^ Cohen, D.S.; Blum, M. On the problem of sorting burnt pancakes. Discrete Applied Mathematics. 1995, 61 (2): 105. doi:10.1016/0166-218X(94)00009-3.
^ Kaplan, H.; Shamir, R.; Tarjan, R.E. Faster and Simpler Algorithm for Sorting Signed Permutations by Reversals. Proc. 8th ACM-SIAM SODA. 1997: 178–187. doi:10.1137/S0097539798334207.
^ Berman, P.; Karpinski, M. On Some Tighter Inapproximability Results. (PDF). Proc. 26th ICALP (1999) LNCS 1644 (Springer). 1999: 200–209.
^ Berman, P.; Karpinski, M.; Hannenhalli, S. 1.375-Approximation Algorithms for Sorting by Reversals. (PDF). Proc. 10th ESA (2002), LNCS 2461 (Springer). 2002: 200–210.
^ Asai, Shogo; Kounoike, Yuusuke; Shinano, Yuji; Kaneko, Keiichi. Computing the Diameter of 17-Pancake Graph Using a PC Cluster.. Euro-Par 2006 Parallel Processing: 12th International Euro-Par Conference. 2006-09-01 [2018-04-06]. doi:10.1007/11823285_117. （原始內容存檔於2019-01-21）.
^ ^19.0 ^19.1 Nguyen, Quan; Bettayeb, Said. On the Genus of Pancake Network. (PDF). The International Arab Journal of Information Technology. 2009-11-05, 8 (3): 289–292. （原始內容存檔 (PDF)於2017-08-09）.
^ Akl, S.G.; Qiu, K.; Stojmenović, I. Fundamental algorithms for the star and pancake interconnection networks with applications to computational geometry.. Networks. 1993, 23 (4): 215–225. doi:10.1002/net.3230230403.
^ Bass, D.W.; Sudborough, I.H. Pancake problems with restricted prefix reversals and some corresponding Cayley networks.. Journal of Parallel and Distributed Computing. March 2003, 63 (3): 327–336. doi:10.1016/S0743-7315(03)00033-9.
^ Berthomé, P.; Ferreira, A.; Perennes, S. Optimal information dissemination in star and pancake networks.. IEEE Transactions on Parallel and Distributed Systems. December 1996, 7 (12): 1292–1300. doi:10.1109/71.553290. （原始內容存檔於2017-08-02）.
^ Kumar, V.; Grama, A.; Gupta, A.; Karypis, G. Introduction to Parallel Computing: Design and Analysis of Algorithms. Benjamin/Cummings. 1994.
^ Quinn, M.J. Parallel Computing: Theory and Practice second. McGraw-Hill. 1994.

拓展閱讀 [編輯]

Heydari, M. H.; Sudborough, I. H. On the Diameter of the Pancake Network. Journal of Algorithms. 1997, 25 (1): 67–94. doi:10.1006/jagm.1997.0874.
Roney-Dougal, C.; Vatter, V. Of Pancakes, Mice and Men. Plus Magazine. March 2010, 54.

外部連結 [編輯]

Cut-the-Knot上的翻煎餅謎題（頁面存檔備份，存於互聯網檔案館），用Java實現的煎餅問題程式，以及一些討論。
道格拉斯·韋斯特講述的煎餅問題（頁面存檔備份，存於互聯網檔案館）
埃里克·韋斯坦因. Pancake Sorting. MathWorld.
一部小動畫，演示了細菌電腦如何解決焦煎餅問題。

[1] Simon Singh. Flipping pancakes with mathematics. The Guardian. 2013-11-14 [2018-04-07]. （原始內容存檔於2017-07-30）.

[2] Fertin, G.; Labarre, A.; Rusu, I.; Tannier, E.; Vialette, S. Combinatorics of Genome Rearrangements. The MIT Press. 2009. ISBN 9780262062824.

[Gates1979-3] 3.0 ^3.1 Gates, W.; Papadimitriou, C. Bounds for Sorting by Prefix Reversal (PDF). Discrete Mathematics. 1979, 27: 47–57 [2018-04-06]. doi:10.1016/0012-365X(79)90068-2. （原始內容 (PDF)存檔於2007-06-10）.

[Sudborough-4] Team Bests Young Bill Gates With Improved Answer to So-Called Pancake Problem in Mathematics. University of Texas at Dallas News Center. 2008-09-17 [2018-04-07]. （原始內容存檔於2012-04-05）. A team of UT Dallas computer science students and their faculty adviser have improved upon a longstanding solution to a mathematical conundrum known as the pancake problem. The previous best solution, which stood for almost 30 years, was devised by Bill Gates and one of his Harvard instructors, Christos Papadimitriou, several years before Microsoft was established.

[5] Chitturi, B.; Fahle, W.; Meng, Z.; Morales, L.; Shields, C. O.; Sudborough, I. H.; Voit, W. An (18/11)n upper bound for sorting by prefix reversals. Theoretical Computer Science. Graphs, Games and Computation: Dedicated to Professor Burkhard Monien on the Occasion of his 65th Birthday. 2009-08-31, 410 (36): 3372–3390 [2018-04-06]. doi:10.1016/j.tcs.2008.04.045. （原始內容存檔於2020-11-11）.

[Bulteau-6] 6.0 ^6.1 Bulteau, Laurent; Fertin, Guillaume; Rusu, Irena. Pancake Flipping Is Hard. Journal of Computer and System Sciences: 1556–1574. arXiv:1111.0434v1 . doi:10.1016/j.jcss.2015.02.003.

[7] Haynes, Karmella A; Broderick, Marian L; Brown, Adam D; Butner, Trevor L; Dickson, James O; Harden, W Lance; Heard, Lane H; Jessen, Eric L; Malloy, Kelly J; Ogden, Brad J; Rosemond, Sabriya; Simpson, Samantha; Zwack, Erin; Campbell, A Malcolm; Eckdahl, Todd T; Heyer, Laurie J; Poet, Jeffrey L. Engineering bacteria to solve the Burnt Pancake Problem. Journal of Biological Engineering. 2008, 2: 8. PMC 2427008 . PMID 18492232. doi:10.1186/1754-1611-2-8.

[8] Hurkens, Cor; van Iersel, Leo; Keijsper, Judith; Kelk, Steven; Stougie, Leen; Tromp, John. Prefix Reversals on Binary and Ternary Strings. SIAM Journal on Discrete Mathematics. 2007-01, 21 (3): 592–611. arXiv:math/0602456 . doi:10.1137/060664252.

[9] B Chitturi, IH Sudborough. Prefix Reversals on Strings (PDF). Proceedings of the International Conference on Bioinformatics & Computational Biology. 2010, 2: 591–598. （原始內容存檔 (PDF)於2018-04-07）.

[:0-10] 10.0 ^10.1 A NOTE ON COMPLEXITY OF GENETIC MUTATIONS. Discrete Mathematics, Algorithms and Applications. 2011, 03 (03): 269–287. doi:10.1142/S1793830911001206.

[11] Dweighter, Harry, Elementary Problem E2569, Amer. Math. Monthly, 1975, 82: 1010, doi:10.2307/2318260

[12] Gargano, L.; Vaccaro, U.; Vozella, A. Fault tolerant routing in the star and pancake interconnection networks. Information Processing Letters. 1993, 45 (6): 315–320. MR 1216942. doi:10.1016/0020-0190(93)90043-9. .

[13] Kaneko, K.; Peng, S. Disjoint paths routing in pancake graphs. Proceedings of Seventh International Conference on Parallel and Distributed Computing, Applications and Technologies, 2006 (PDCAT '06). 2006: 254–259. ISBN 0-7695-2736-1. doi:10.1109/PDCAT.2006.56. .

[14] Cohen, D.S.; Blum, M. On the problem of sorting burnt pancakes. Discrete Applied Mathematics. 1995, 61 (2): 105. doi:10.1016/0166-218X(94)00009-3.

[15] Kaplan, H.; Shamir, R.; Tarjan, R.E. Faster and Simpler Algorithm for Sorting Signed Permutations by Reversals. Proc. 8th ACM-SIAM SODA. 1997: 178–187. doi:10.1137/S0097539798334207.

[16] Berman, P.; Karpinski, M. On Some Tighter Inapproximability Results. (PDF). Proc. 26th ICALP (1999) LNCS 1644 (Springer). 1999: 200–209.

[17] Berman, P.; Karpinski, M.; Hannenhalli, S. 1.375-Approximation Algorithms for Sorting by Reversals. (PDF). Proc. 10th ESA (2002), LNCS 2461 (Springer). 2002: 200–210.

[pancake17-18] Asai, Shogo; Kounoike, Yuusuke; Shinano, Yuji; Kaneko, Keiichi. Computing the Diameter of 17-Pancake Graph Using a PC Cluster.. Euro-Par 2006 Parallel Processing: 12th International Euro-Par Conference. 2006-09-01 [2018-04-06]. doi:10.1007/11823285_117. （原始內容存檔於2019-01-21）.

[ongenus-19] 19.0 ^19.1 Nguyen, Quan; Bettayeb, Said. On the Genus of Pancake Network. (PDF). The International Arab Journal of Information Technology. 2009-11-05, 8 (3): 289–292. （原始內容存檔 (PDF)於2017-08-09）.

[20] Akl, S.G.; Qiu, K.; Stojmenović, I. Fundamental algorithms for the star and pancake interconnection networks with applications to computational geometry.. Networks. 1993, 23 (4): 215–225. doi:10.1002/net.3230230403.

[21] Bass, D.W.; Sudborough, I.H. Pancake problems with restricted prefix reversals and some corresponding Cayley networks.. Journal of Parallel and Distributed Computing. March 2003, 63 (3): 327–336. doi:10.1016/S0743-7315(03)00033-9.

[22] Berthomé, P.; Ferreira, A.; Perennes, S. Optimal information dissemination in star and pancake networks.. IEEE Transactions on Parallel and Distributed Systems. December 1996, 7 (12): 1292–1300. doi:10.1109/71.553290. （原始內容存檔於2017-08-02）.

[23] Kumar, V.; Grama, A.; Gupta, A.; Karypis, G. Introduction to Parallel Computing: Design and Analysis of Algorithms. Benjamin/Cummings. 1994.

[24] Quinn, M.J. Parallel Computing: Theory and Practice second. McGraw-Hill. 1994.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

高度 $n$	$k$
高度 $n$	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