煎餅排序：修订间差异

删除的内容添加的内容

行内

2024年11月3日 (日) 23:42的最新版本

煎饼排序（英語：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]

@@ 第1行： / 第1行： @@
+{{NoteTA
-[[File:Pancake sort operation.png|right|frame|Demonstration of the primary operation. The spatula is flipping over the top three pancakes, with the result seen below. In the burnt pancake problem, their top sides would now be burnt instead of their bottom sides.]]
+|G1 = IT
+|G2 = Math
+|1 = zh-cn:飞出个未来; zh-tw:飛出個未來; zh-hk:乃出個未來;
+|2 = 摞=>zh-tw:疊;
+}}
+[[File:Pancake sort operation.png|right|frame|一次示例操作。上方是用煎饼铲子将顶上三张煎饼翻面，翻完以后变为下方所示的状态。在焦煎饼问题中，如果原来三张饼的焦面朝下，则翻完之后变为焦面朝上]]
-'''煎饼排序''' is the colloquial term for the mathematical problem of sorting a disordered stack of pancakes in order of size when a {{tsl|en|spatula||}} can be inserted at any point in the stack and used to flip all pancakes above it.  A ''pancake number'' is the minimum number of flips required for a given number of pancakes. In this form, the problem was first discussed by [[美国|American]] [[几何学家列表|几何学家列表]] {{tsl|en|Jacob E. Goodman||}}.<ref>{{cite news|author=Simon Singh| title=Flipping pancakes with mathematics|newspaper=[[衛報|]]| date=November 14, 2013| url=https://www.theguardian.com/science/blog/2013/nov/14/flipping-pancakes-mathematics-jacob-goodman| accessdate=March 25, 2014}}</ref> It is a variation of the [[排序算法|sorting]] problem in which the only allowed operation is to reverse the elements of some ''{{tsl|en|prefix (computer science)||prefix}}'' of the sequence. Unlike a traditional sorting algorithm, which attempts to sort with the fewest comparisons possible, the goal is to sort the sequence in as few reversals as possible. A variant of the problem is concerned with ''burnt'' pancakes, where each pancake has a burnt side and all pancakes must, in addition, end up with the burnt side on bottom.
+'''煎饼排序'''（{{lang-en|Pancake sorting}}）指的是将大小不同的一摞煎饼按大小排序的数学问题，其中{{link-en|抹刀|spatula}}每次只能从任意位置铲起上方全部煎饼并翻面。“煎饼数”（{{lang-en|pancake number}}）是指给定煎饼的张数时，最坏情况下需要的最少翻面次数。这个问题最早由[[美国]]几何学家[[雅各布·E·古德曼]]提出。<ref>{{cite news| author=Simon Singh| title=Flipping pancakes with mathematics| newspaper=[[衛報|The Guardian]]| date=2013-11-14| url=https://www.theguardian.com/science/blog/2013/nov/14/flipping-pancakes-mathematics-jacob-goodman| accessdate=2018-04-07| deadurl=no| archiveurl=https://web.archive.org/web/20170730232025/https://www.theguardian.com/science/blog/2013/nov/14/flipping-pancakes-mathematics-jacob-goodman| archivedate=2017-07-30}}</ref>它属于[[排序算法|排序问题]]的变种。煎饼排序的目标和传统排序算法最小化比较次数不同，因为它每次操作只允许反转序列的{{tsl|en|prefix (computer science)|前缀 (计算机科学)|前缀}}，所以需要最小化反转前缀次数。焦煎饼排序是煎饼排序的变种问题，每张煎饼都有一面是烤焦的，最终除了按照大小排序以外还要让所有焦面向下。
 == 煎饼问题 ==
@@ 第10行： / 第16行： @@
 最简单的算法在最坏情况下需要{{math|2''n''{{thinsp}}&minus;{{thinsp}}3}}次翻转。这种算法是[[选择排序]]的变体，每轮用一次翻转把未排序的煎饼中最大者翻到顶上，再用一次翻转把它翻到最终所在处（目前未排序煎饼和已排序煎饼的交界处），然后对剩余未排序煎饼重复此过程。剩下两个煎饼时只需一次翻转即完成排序。
-年[[比尔·盖茨]]和[[赫里斯托斯·帕帕季米特里乌]]<ref name=Gates1979/>给出了一个上界{{math|{{sfrac|(5''n''+5)|3}}}}。三十年后[[德克薩斯州大學達拉斯分校]]Hal Sudborough教授领导的一组研究者将这个上界改进为{{math|{{sfrac|18|11}}''n''}}<ref name="Sudborough">{{cite web|title=Team Bests Young Bill Gates With Improved Answer to So-Called Pancake Problem in Mathematics|publisher=University of Texas at Dallas News Center|date=September 17, 2008|url=http://www.utdallas.edu/news/2008/09/17-002.php?WT.mc_id=NewsEmails&WT.mc_ev=EmailOpen|accessdate=November 10, 2008|quote=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.}}</ref><ref>{{Cite journal|last=Chitturi|first=B.|last2=Fahle|first2=W.|last3=Meng|first3=Z.|last4=Morales|first4=L.|last5=Shields|first5=C. O.|last6=Sudborough|first6=I. H.|last7=Voit|first7=W.|date=2009-08-31|title=An (18/11)n upper bound for sorting by prefix reversals|url=http://www.sciencedirect.com/science/article/pii/S0304397508003575|journal=Theoretical Computer Science|series=Graphs, Games and Computation: Dedicated to Professor Burkhard Monien on the Occasion of his 65th Birthday|volume=410|issue=36|pages=3372–3390|doi=10.1016/j.tcs.2008.04.045}}</ref>。
+年[[比尔·盖茨]]和[[赫里斯托斯·帕帕季米特里乌]]给出了一个上界{{math|{{sfrac|5''n''+5|3}}}}<ref name=Gates1979/>。三十年后[[德克薩斯州大學達拉斯分校]]萨薄若（Sudborough）教授领导的一组研究者将这个上界改进为{{math|{{sfrac|18|11}}''n''}}<ref name="Sudborough">{{cite web|title=Team Bests Young Bill Gates With Improved Answer to So-Called Pancake Problem in Mathematics|publisher=University of Texas at Dallas News Center|date=2008-09-17|url=http://www.utdallas.edu/news/2008/09/17-002.php?WT.mc_id=NewsEmails&WT.mc_ev=EmailOpen|accessdate=2018-04-07|quote=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.|deadurl=yes|archiveurl=https://www.webcitation.org/66htPePZH?url=http://www.utdallas.edu/news/2008/09/17-002.php?WT.mc_id=NewsEmails|archivedate=2012-04-05}}</ref><ref>{{Cite journal|last=Chitturi|first=B.|last2=Fahle|first2=W.|last3=Meng|first3=Z.|last4=Morales|first4=L.|last5=Shields|first5=C. O.|last6=Sudborough|first6=I. H.|last7=Voit|first7=W.|date=2009-08-31|title=An (18/11)n upper bound for sorting by prefix reversals|url=http://www.sciencedirect.com/science/article/pii/S0304397508003575|journal=Theoretical Computer Science|series=Graphs, Games and Computation: Dedicated to Professor Burkhard Monien on the Occasion of his 65th Birthday|volume=410|issue=36|pages=3372–3390|doi=10.1016/j.tcs.2008.04.045|access-date=2018-04-06|archive-date=2020-11-11|archive-url=https://web.archive.org/web/20201111215446/https://www.sciencedirect.com/science/article/pii/S0304397508003575|dead-url=no}}</ref>。
-年，Laurent Bulteau、Guillaume Fertin和Irena Rusu<ref>{{Cite journal|journal=Journal of Computer and System Sciences|doi=10.1016/j.jcss.2015.02.003|title=Pancake Flipping Is Hard|last1=Bulteau|first1=Laurent|last2=Fertin|first2=Guillaume|last3=Rusu|first3=Irena|volume=81|number=8|pages=1556–1574|arxiv=1111.0434v1}}</ref>证明了给定一叠煎饼的长度分布，找到最短解法是[[NP困难]]的，最终解决了这个已提出三十余年的问题。
+年，劳伦特·比尔托（Laurent Bulteau）、纪尧姆·佛丁（Guillaume Fertin）和伊雷娜·鲁苏（Irena Rusu）证明了给定一叠煎饼的长度分布，找到最短解法是[[NP困难]]的，最终解决了这个已提出三十余年的问题。<ref name="Bulteau">{{Cite journal|journal=Journal of Computer and System Sciences|doi=10.1016/j.jcss.2015.02.003|title=Pancake Flipping Is Hard|last1=Bulteau|first1=Laurent|last2=Fertin|first2=Guillaume|last3=Rusu|first3=Irena|volume=81|number=8|pages=1556–1574|arxiv=1111.0434v1}}</ref>
 === 焦煎饼问题 ===
-'''焦煎饼问题'''（{{lang-en|'''burnt pancake problem'''}}是煎饼问题的一种变体，其中每个煎饼有一面是焦的，排序后必须使所有煎饼焦的一面朝下。这是一类带符号的排列问题（{{lang-en|signed permutation}}），如果某个煎饼''i''焦的一面朝上，就在排列中给它加一个符号，记为''i`''。2008年，一组本科生对[[大腸桿菌]]编程，构造[[DNA運算]|细菌计算机]]让其翻转类似焦煎饼的DNA序列，解决了一个简单的焦煎饼问题。DNA具有[[方向性 (分子生物学)|方向性]]（5‘端和3‘端）和顺序（[[啟動子]]和编码区）。虽然细菌对DNA翻转的处理能力较弱，但单次培养中为数众多的细菌提供了巨大的并行计算平台。细菌回报它们已经解决问题的方法是使自己带有[[抗生素抗藥性]]。<ref>{{Cite journal|doi=10.1186/1754-1611-2-8|title=Engineering bacteria to solve the Burnt Pancake Problem|year=2008|last1=Haynes|first1=Karmella A|last2=Broderick|first2=Marian L|last3=Brown|first3=Adam D|last4=Butner|first4=Trevor L|last5=Dickson|first5=James O|last6=Harden|first6=W Lance|last7=Heard|first7=Lane H|last8=Jessen|first8=Eric L|last9=Malloy|first9=Kelly J|journal=Journal of Biological Engineering|volume=2|pages=8|pmid=18492232|pmc=2427008|last10=Ogden|first10=Brad J|last11=Rosemond|first11=Sabriya|last12=Simpson|first12=Samantha|last13=Zwack|first13=Erin|last14=Campbell|first14=A Malcolm|last15=Eckdahl|first15=Todd T|last16=Heyer|first16=Laurie J|last17=Poet|first17=Jeffrey L}}</ref>
+焦煎饼问题（{{lang-en|Burnt pancake problem}}）是煎饼问题的一种变体，其中每个煎饼有一面是焦的，排序后必须使所有煎饼焦的一面朝下。这是一类带符号的排列问题（{{lang-en|signed permutation}}），如果某个煎饼焦的一面朝上，就在排列中给它加一个符号，最后结果必须不含符号。2008年，一组本科生对[[大腸桿菌]]-{zh-cn:编程;zh-tw:程式設計;}-，构造[[DNA運算|细菌计算机]]让其翻转类似焦煎饼的DNA序列，解决了一个简单的焦煎饼问题。DNA具有[[方向性 (分子生物学)|方向性]]（5'端和3'端）和顺序（[[啟動子]]和编码区）。虽然细菌对DNA翻转的处理能力较弱，但单次培养中为数众多的细菌提供了庞大的并行计算平台。當细菌帶有[[抗生素抗藥性]]時，DNA序列的排序問題即告解決。<ref>{{Cite journal|doi=10.1186/1754-1611-2-8|title=Engineering bacteria to solve the Burnt Pancake Problem|year=2008|last1=Haynes|first1=Karmella A|last2=Broderick|first2=Marian L|last3=Brown|first3=Adam D|last4=Butner|first4=Trevor L|last5=Dickson|first5=James O|last6=Harden|first6=W Lance|last7=Heard|first7=Lane H|last8=Jessen|first8=Eric L|last9=Malloy|first9=Kelly J|journal=Journal of Biological Engineering|volume=2|pages=8|pmid=18492232|pmc=2427008|last10=Ogden|first10=Brad J|last11=Rosemond|first11=Sabriya|last12=Simpson|first12=Samantha|last13=Zwack|first13=Erin|last14=Campbell|first14=A Malcolm|last15=Eckdahl|first15=Todd T|last16=Heyer|first16=Laurie J|last17=Poet|first17=Jeffrey L}}</ref>
+== 字符串中的煎饼问题 ==
-===The identical pancakes stack problem===
+如果将煎饼摞视为一个字符串，每次翻转相当于取一段前缀并将其反转，这是一个[[置換]]操作。不过，前述讨论假定每个煎饼都是不同的，但是字符串可以包含相同字符，因此前缀反转所需次数可能会减少。赫肯斯（Hurkens）等人在2007年构造了二元和三元字符串前缀反转排序的多项式时间精确算法<ref>{{cite journal|title=Prefix Reversals on Binary and Ternary Strings|first1=Cor|last2=van Iersel|first2=Leo|date=2007-01|journal=SIAM Journal on Discrete Mathematics|issue=3|doi=10.1137/060664252|volume=21|pages=592–611|arxiv=math/0602456|last3=Keijsper|first3=Judith|last4=Kelk|first4=Steven|last5=Stougie|first5=Leen|last6=Tromp|first6=John|last1=Hurkens}}</ref>，并证明了用最少的前缀反转次数将一个二元字符串变换为另一个二元字符串是[[NP困难]]的。池图瑞（Chitturi）等人<ref>{{cite journal|title=Prefix Reversals on Strings|url=https://www.researchgate.net/profile/Bhadrachalam_Chitturi/publication/221051667_Prefix_Reversals_on_Strings/links/57b4521008aeddbf36e6da4b.pdf|date=2010|journal=Proceedings of the International Conference on Bioinformatics & Computational Biology|volume=2|pages=591-598|archiveurl=https://web.archive.org/web/20180407162915/https://www.researchgate.net/profile/Bhadrachalam_Chitturi/publication/221051667_Prefix_Reversals_on_Strings/links/57b4521008aeddbf36e6da4b.pdf|archivedate=2018-04-07|deadurl=no|author1=B Chitturi, IH Sudborough}}</ref>于2010年将上述结论推广到了一般字符串，证明了它是[[NP完全]]的，并给出了最少次数的上下界。池图瑞在2011年证明了带符号的字符串前缀反转排序（即字符串中的焦煎饼问题）也是NP完全的<ref name=":0" />。
-This is inspired from the way Indian bread ({{tsl|en|Roti||}} or [[印度烤餅|印度烤餅]]) is cooked. Initially, all rotis are stacked in one column, and the cook uses a spatula to flip the rotis so that each side of each roti touches the base fire at some point to toast. Several variants are possible: the rotis can be considered as single-sided or two-sided, and it may be forbidden or not to toast the same side twice. This version of the problem was first explored by Arka Roychowdhury.<ref>{{cite web|title=Itunes: Flipping Pancakes|first=Arka|last=Roychowdhury|url=https://arkaroychowdhury1.wordpress.com/portfolio/flippingpancakes/|website=Crazy1S}}</ref>
-==The pancake problem on strings==
-The discussion above presumes that each pancake is unique, that is, the sequence on which the prefix reversals are performed is a ''[[置換|置換]]''. However, "strings" are sequences in which a symbol can repeat, and this repetition may reduce the number of prefix reversals required to sort. Chitturi and Sudborough (2010) and Hurkens et al. (2007) independently showed that the complexity of transforming a compatible string into another with the minimum number of prefix reversals is [[NP困难|NP困难]]. They also gave bounds for the same. Hurkens et al. gave an exact algorithm to sort binary and ternary strings. Chitturi<ref name=":0" />  (2011) proved that the complexity of transforming a compatible signed string into another with the minimum number of signed prefix reversals—the burnt pancake problem on strings—is NP-hard.
 == 历史 ==
-The pancake sorting problem was first posed by {{tsl|en|Jacob E. Goodman||}}, writing under the pseudonym "Harry Dweighter" (harried waiter).<ref>{{citation
+煎饼排序问题最初由{{tsl|en|Jacob E. Goodman|雅可比·E·古德曼|雅可比·古德曼}}提出，他当时用了假名“哈利·德威特”（原文“{{lang|en|Harry Dweighter}}”，音近“{{lang|en|harried waiter}}”，即“忙亂的侍應”）。<ref>{{citation
 |first1=Harry|last1=Dweighter
 |title= Elementary Problem E2569
@@ 第34行： / 第37行： @@
 </ref>
+煎饼问题更多地在教育中见到，但也会在并行处理网络中用到，它的解答对应着处理器之间高效的最短路算法。<ref>{{Cite journal| last1 = Gargano | first1 = L.
-Although seen more often as an educational device, pancake sorting also appears in applications in parallel processor networks, in which it can provide an effective routing algorithm between processors.<ref>{{Cite journal| last1 = Gargano | first1 = L.
  | last2 = Vaccaro | first2 = U.
  | last3 = Vozella | first3 = A.
@@ 第44行： / 第47行： @@
  | title = Fault tolerant routing in the star and pancake interconnection networks
  | volume = 45
- | year = 1993| postscript = <!-- Bot inserted parameter. Either remove it; or change its value to "." for the cite to end in a ".", as necessary. -->{{inconsistent citations}} }}.</ref><ref>{{Cite book| last1 = Kaneko | first1 = K.
+ | year = 1993}}.</ref><ref>{{Cite book| last1 = Kaneko | first1 = K.
  | last2 = Peng | first2 = S.
  | contribution = Disjoint paths routing in pancake graphs
@@ 第50行： / 第53行： @@
  | pages = 254–259
  | title = Proceedings of Seventh International Conference on Parallel and Distributed Computing, Applications and Technologies, 2006 (PDCAT '06)
+ | year = 2006| isbn = 0-7695-2736-1}}.</ref>这个问题也在计算生物学中有所应用<ref name="Bulteau" />。
- | year = 2006| isbn = 0-7695-2736-1 | postscript = <!-- Bot inserted parameter. Either remove it; or change its value to "." for the cite to end in a ".", as necessary. -->{{inconsistent citations}} }}.</ref>
-The problem is notable as the topic of the only well-known mathematics paper by [[微软|微软]] founder [[比尔·盖茨|比尔·盖茨]] (as William Gates), entitled "Bounds for Sorting by Prefix Reversal". Published in 1979, it describes an efficient algorithm for pancake sorting.<ref name=Gates1979>{{cite journal |url=http://www.cs.berkeley.edu/~christos/papers/Bounds%20For%20Sorting%20By%20Prefix%20Reversal.pdf |title=Bounds for Sorting by Prefix Reversal |journal={{tsl|en|Discrete Mathematics (journal)||Discrete Mathematics}} |volume=27 |pages=47–57 |year=1979 |doi=10.1016/0012-365X(79)90068-2 |last=Gates |first=W. |last2=Papadimitriou |first2=C. |authorlink1 = Bill Gates |authorlink2 = Christos Papadimitriou}}</ref> In addition, the most notable paper published by ''[[乃出個未來|乃出個未來]]'' co-creator {{tsl|en|David X. Cohen||}} (as David S. Cohen) concerned the burnt pancake problem.<ref>{{Cite journal|last1=Cohen|first1=D.S. |last2= Blum|first2=M.|doi=10.1016/0166-218X(94)00009-3|title=On the problem of sorting burnt pancakes|year=1995|journal=Discrete Applied Mathematics|volume=61|issue=2|pages=105|authorlink1=David X. Cohen|authorlink2=Manuel Blum}}</ref> Their collaborators were [[赫里斯托斯·帕帕季米特里乌|赫里斯托斯·帕帕季米特里乌]] (then at [[哈佛大学|Harvard]], now at [[哥伦比亚大学|Columbia]]) and [[曼纽尔·布卢姆|曼纽尔·布卢姆]] (then at [[加利福尼亞大學柏克萊分校|Berkeley]], now at [[卡内基·梅隆大学|卡内基·梅隆大学]]), respectively.
+[[微软]]公司创立者[[比尔·盖茨]]就这个问题在1979年发表过一篇题为《前缀逆转排序的边界问题》（{{lang-en|''Bounds for Sorting by Prefix Reversal''}}）的论文，这是他唯一广为人知的数学论文。在这篇论文中盖茨描述了一种高效的煎饼排序算法。<ref name=Gates1979>{{cite journal |url=http://www.cs.berkeley.edu/~christos/papers/Bounds%20For%20Sorting%20By%20Prefix%20Reversal.pdf |title=Bounds for Sorting by Prefix Reversal |journal=Discrete Mathematics |volume=27 |pages=47–57 |year=1979 |doi=10.1016/0012-365X(79)90068-2 |last=Gates |first=W. |last2=Papadimitriou |first2=C. |deadurl=yes |archiveurl=https://web.archive.org/web/20070610154429/http://www.cs.berkeley.edu/~christos/papers/Bounds%20For%20Sorting%20By%20Prefix%20Reversal.pdf |archivedate=2007-06-10 |author= |access-date=2018-04-06 }}</ref>另外，《[[乃出個未來]]》的主創之一{{tsl|en|David X. Cohen|大卫·X·科恩|大卫·科恩}}研究了焦煎饼问题。<ref>{{Cite journal|last1=Cohen|first1=D.S. |last2= Blum|first2=M.|doi=10.1016/0166-218X(94)00009-3|title=On the problem of sorting burnt pancakes|year=1995|journal=Discrete Applied Mathematics|volume=61|issue=2|pages=105}}</ref>他们两位的合作者分别是[[赫里斯托斯·帕帕季米特里乌]]（当时在[[哈佛大学]]任职，目前在[[哥伦比亚大学]]）与[[曼纽尔·布卢姆]]（当时在[[加利福尼亞大學柏克萊分校]]任职，目前在[[卡内基·梅隆大学]]）。
-The connected problems of signed sorting by reversals and sorting by reversals were also studied more recently. Whereas efficient exact algorithms have been found for the signed sorting by reversals,<ref>{{cite journal|last1=Kaplan|first1=H.|last2=Shamir|first2=R.|author3-link=Robert Tarjan|last3=Tarjan|first3=R.E.|title=Faster and Simpler Algorithm for Sorting Signed Permutations by Reversals|journal=''Proc.'' 8th ''ACM-SIAM SODA''|date=1997|pages=178-87}}</ref> the problem of sorting by reversals has been proven to be hard even to approximate to within certain constant factor,<ref>{{cite journal|last1=Berman|first1=P.|author2-link=Marek Karpinski|last2=Karpinski|first2=M.|url=http://theory.cs.uni-bonn.de/ftp/reports/cs-reports/1998/85193-CS.ps.gz|title=On Some Tighter Inapproximability Results.|journal=''Proc.'' 26th ''ICALP'' (1999) LNCS 1644|year=1999|publisher=Springer|pages=200-09}}</ref> and also proven to be approximable in polynomial time to within the approximation factor 1.375.<ref>{{cite journal|last=Berman|first=P.|author2-link=Marek Karpinski|last2=Karpinski|first2=M.|last3=Hannenhalli|first3=S.|url=http://theory.cs.uni-bonn.de/ftp/reports/cs-reports/2001/85228-CS.ps.gz|title=1.375-Approximation Algorithms for Sorting by Reversals.|journal=''Proc.'' 10th ''ESA'' (2002), ''LNCS'' 2461|publisher=Springer|pages=200-10|year=2002}}</ref>
+之后，相关的字符串子串反转排序问题也得到了研究。不过，带符号的子串反转排序问题有[[多项式时间|平方时间]]的精确算法<ref>{{cite journal|last1=Kaplan|first1=H.|last2=Shamir|first2=R.|last3=Tarjan|first3=R.E.|title=Faster and Simpler Algorithm for Sorting Signed Permutations by Reversals|journal=''Proc.'' 8th ''ACM-SIAM SODA''|date=1997|pages=178-187|doi=10.1137/S0097539798334207}}</ref>，但（不带符号的）子串反转问题不存在多项式时间的精确算法，其多项式时间[[近似算法]]的近似因子下界为1.0008，上界为1.5<ref>{{cite journal|last1=Berman|first1=P.|last2=Karpinski|first2=M.|url=https://link.springer.com/content/pdf/10.1007%2F3-540-48523-6.pdf|title=On Some Tighter Inapproximability Results.|journal=''Proc.'' 26th ''ICALP'' (1999) LNCS 1644|year=1999|publisher=Springer|pages=200-209}}</ref>，后来找到了近似因子为1.375的多项式时间近似算法<ref>{{cite journal|last=Berman|first=P.|last2=Karpinski|first2=M.|last3=Hannenhalli|first3=S.|url=https://link.springer.com/content/pdf/10.1007%2F3-540-45749-6.pdf|title=1.375-Approximation Algorithms for Sorting by Reversals.|journal=''Proc.'' 10th ''ESA'' (2002), ''LNCS'' 2461|publisher=Springer|pages=200-210|year=2002}}</ref>。
 == 煎饼图 ==
-[[File:Pancake graph g3.svg|thumb|The pancake graph P<sub>3</sub> ]]
+[[File:Pancake graph g3.svg|thumb|煎饼图P<sub>3</sub>]]
-[[File:Pancake graph g4.svg|thumb|The pancake graph P<sub>4</sub> can be constructed recursively from 4 copies of P<sub>3</sub> by assigning a different element from the set {1, 2, 3, 4} as a suffix to each copy.]]
+[[File:Pancake graph g4.svg|thumb|煎饼图P<sub>4</sub>可以用4个P<sub>3</sub>递归地构造：给每个子图编号1、2、3、4，编号为i的子图每个[[顶点 (图论)|顶点]]对应的排列为1－4除去i的全排列，末尾加上i]]
-{{main|Pancake graph}}
+{{main|{{tsl|en|Pancake graph|煎饼图}}}}
-An '''''n''-pancake graph''' is a graph whose vertices are the permutations of ''n'' symbols from 1 to ''n'' and its edges are given between permutations transitive by prefix reversals. It is a [[正則圖|正則圖]] with n! vertices, its degree is n&minus;1. The pancake sorting problem and the problem to obtain the {{tsl|en|Distance (graph theory)||diameter}} of the pancake graph is equivalent.<ref name="pancake17">{{Cite journal|last=Asai|first=Shogo|last2=Kounoike|first2=Yuusuke||last3=Shinano|first3=Yuji|last4=Kaneko|first4=Keiichi|date=2006-09-01|title=Computing the Diameter of 17-Pancake Graph Using a PC Cluster.|url=https://link.springer.com/chapter/10.1007/11823285_117 |journal=Euro-Par 2006 Parallel Processing: 12th International Euro-Par Conference|doi=10.1007/11823285_117}}</ref>
+n-煎饼图的[[顶点 (图论)|顶点]]用1到n的全排列编号，两个顶点之间有边当且仅当两个顶点对应的排列可以由前缀反转得到。它是n!个顶点的[[正則圖]]，度数为n&minus;1。煎饼排序问题等价于求取煎饼图的[[距离#圖論|直径]]。<ref name="pancake17">{{Cite journal|last=Asai|first=Shogo|last2=Kounoike|first2=Yuusuke|5=|last3=Shinano|first3=Yuji|last4=Kaneko|first4=Keiichi|date=2006-09-01|title=Computing the Diameter of 17-Pancake Graph Using a PC Cluster.|url=https://link.springer.com/chapter/10.1007/11823285_117|journal=Euro-Par 2006 Parallel Processing: 12th International Euro-Par Conference|doi=10.1007/11823285_117|access-date=2018-04-06|archive-date=2019-01-21|archive-url=https://web.archive.org/web/20190121064118/https://link.springer.com/chapter/10.1007/11823285_117|dead-url=no}}</ref>
+n-煎饼图记为P<sub>n</sub>，可以使用n个P<sub>n&minus;1</sub>递归地构建：给每个子煎饼图分别编号1、2、……、n，编号为i的子图每个[[顶点 (图论)|顶点]]对应的排列为1－n这n个数除去i的全排列，末尾加上i。
-The pancake graph of dimension ''n'', P<sub>n</sub> can be constructed recursively from n copies of P<sub>n&minus;1</sub>, by assigning a different element from the set {1, 2, …, n} as a suffix to each copy.
-Their [[圍長 (圖論)|girth]]:
+三阶及以上的煎饼图[[圍長 (圖論)|围长]]恒为6：
-<math>g(P_n) = 6 \text{, if } n>2</math>.
+<math>g(P_n) = 6 \text{, if } n>2</math>
-The &gamma;(P<sub>n</sub>) [[圖嵌入|genus]] of P<sub>n</sub> is<ref name="ongenus">{{Cite journal|last=Nguyen|first=Quan|last2=Bettayeb|first2=Said|date=2009-11-05|title=On the Genus of Pancake Network.|url=http://ccis2k.org/iajit/PDF/vol.8,no.3/1247.pdf |journal=The International Arab Journal of Information Technology |volume=8|issue=3|pages=289–292}}</ref>:
+P<sub>n</sub>的[[亏格]]&gamma;(P<sub>n</sub>)为：<ref name="ongenus">{{Cite journal|last=Nguyen|first=Quan|last2=Bettayeb|first2=Said|date=2009-11-05|title=On the Genus of Pancake Network.|url=http://ccis2k.org/iajit/PDF/vol.8,no.3/1247.pdf|journal=The International Arab Journal of Information Technology|volume=8|issue=3|pages=289–292|deadurl=no|archiveurl=https://web.archive.org/web/20170809203553/http://ccis2k.org/iajit/PDF/vol.8,no.3/1247.pdf|archivedate=2017-08-09}}</ref>
 <math>n!\left( \frac{n-4}{6} \right)+1 \le \gamma(P_n) \le n!\left( \frac{n-3}{4} \right)-\frac{n}{2}+1 </math>
-Since pancake graphs have many interesting properties such as symmetric and recursive structures, small degrees and diameters compared against the size of the graph, much attention is paid to them as a model of interconnection networks for parallel computers<ref>{{Cite journal|last=Akl|first=S.G.|last2=Qiu|first2=K.|last3=Stojmenović|first3=I.|date=1993|title=Fundamental algorithms for the star and pancake interconnection networks with applications to computational geometry.|url=http://onlinelibrary.wiley.com/doi/10.1002/net.3230230403|journal=Networks|volume=23|issue=4|pages=215–225|doi=10.1002/net.3230230403}}</ref><ref>{{Cite journal|last=Bass|first=D.W.|last2=Sudborough|first2=I.H.|date=March 2003|title=Pancake problems with restricted prefix reversals and some corresponding Cayley networks.|url=https://dx.doi.org/10.1016/S0743-7315(03)00033-9|journal=Journal of Parallel and Distributed Computing |volume=63|issue=3|pages=327–336|doi=10.1016/S0743-7315(03)00033-9}}</ref><ref>{{Cite journal|last=Berthomé|first=P.|last2=Ferreira|first2=A.|last3=Perennes|first3=S.|date=December 1996|title=Optimal information dissemination in star and pancake networks.|url=http://ieeexplore.ieee.org/document/553290/|journal=IEEE Transactions on Parallel and Distributed Systems|volume=7|issue=12|pages=1292–1300|doi=10.1109/71.553290}}</ref>. When we regard the pancake graphs as the model of the interconnection networks, the diameter of the graph is a measure that represents the delay of communication<ref>{{cite book|last1=Kumar|first1=V.|last2=Grama|first2=A.|last3=Gupta|first3=A.|last4=Karypis|first4=G.|title=Introduction to Parallel Computing: Design and Analysis of Algorithms|publisher=Benjamin/Cummings|date=1994}}</ref><ref>{{cite book|last=Quinn|first=M.J.|title=Parallel Computing: Theory and Practice|edition=second|publisher=McGraw-Hill|date=1994}}</ref>.
+煎饼图有许多有趣的性质，例如对称性和上文所述的递归结构。另外，它是[[凱萊圖]]，因此也是{{tsl|en|Vertex-transitive graph|顶点传递图|顶点传递图}}。随着维度的增加，煎饼图的度数和直径都以低于对数的速度增长，因此它比{{tsl|en|Hypercube graph|超方形图|超方形图}}等图更为{{tsl|en|Dense graph|稠密图|稀疏}}。<ref name="ongenus" />人们对其在并行计算的互连网络模型的应用非常关注。<ref>{{Cite journal|last=Akl|first=S.G.|last2=Qiu|first2=K.|last3=Stojmenović|first3=I.|date=1993|title=Fundamental algorithms for the star and pancake interconnection networks with applications to computational geometry.|url=http://onlinelibrary.wiley.com/doi/10.1002/net.3230230403|journal=Networks|volume=23|issue=4|pages=215–225|doi=10.1002/net.3230230403}}</ref><ref>{{Cite journal|last=Bass|first=D.W.|last2=Sudborough|first2=I.H.|date=March 2003|title=Pancake problems with restricted prefix reversals and some corresponding Cayley networks.|url=https://dx.doi.org/10.1016/S0743-7315(03)00033-9|journal=Journal of Parallel and Distributed Computing |volume=63|issue=3|pages=327–336|doi=10.1016/S0743-7315(03)00033-9}}</ref><ref>{{Cite journal|last=Berthomé|first=P.|last2=Ferreira|first2=A.|last3=Perennes|first3=S.|date=December 1996|title=Optimal information dissemination in star and pancake networks.|url=http://ieeexplore.ieee.org/document/553290/|journal=IEEE Transactions on Parallel and Distributed Systems|volume=7|issue=12|pages=1292–1300|doi=10.1109/71.553290|deadurl=no|archiveurl=https://web.archive.org/web/20170802110811/http://ieeexplore.ieee.org/document/553290/|archivedate=2017-08-02}}</ref>如果把煎饼图视为互连网络的模型，它的直径大小可以衡量通信延迟高低<ref>{{cite book|last1=Kumar|first1=V.|last2=Grama|first2=A.|last3=Gupta|first3=A.|last4=Karypis|first4=G.|title=Introduction to Parallel Computing: Design and Analysis of Algorithms|publisher=Benjamin/Cummings|date=1994}}</ref><ref>{{cite book|last=Quinn|first=M.J.|title=Parallel Computing: Theory and Practice|url=https://archive.org/details/parallelcomputin0000quin|edition=second|publisher=McGraw-Hill|date=1994}}</ref>。
-The pancake graphs are [[凱萊圖|凱萊圖]]s (thus are {{tsl|en|Vertex-transitive graph||vertex-transitive}}) and are especially attractive for parallel processing. They have sublogarithmic degree and diameter, and are relatively {{tsl|en|Dense graph||sparse}} (compared to e.g. {{tsl|en|Hypercube graph||hypercubes}})<ref name="ongenus"/>.
 == 相关整数序列 ==
 :{| class="wikitable" align="center" style="float: center; text-align: right;"
 |+ 给定一叠{{math|''n''}}个煎饼，有多少种长度排列可以在翻{{math|''k''}}次以内排好序
-! rowspan=2 | Height<br />{{math|''n''}} !! colspan=16 | {{math|''k''}}
+! rowspan=2 | 高度<br />{{math|''n''}} !! colspan=16 | {{math|''k''}}
 |-
 ! width="65px" |  0 !! width="65px" |  1 !! width="65px" |  2 !! width="65px" |  3 !! width="65px" |  4 !! width="65px" |  5 !! width="65px" |  6 !! width="65px" | 7
@@ 第124行： / 第125行： @@
 |}
-[[尼爾·斯洛恩]]的[[整數數列線上大全]]中的一些序列<ref name=":0">{{cite journal|title=A NOTE ON COMPLEXITY OF GENETIC MUTATIONS|journal=Discrete Mathematics, Algorithms and Applications|volume= 03| issue = 03|doi=10.1142/S1793830911001206}}</ref>：
+在[[整數數列線上大全]]中，有一些序列与煎饼排序有关<ref name=":0">{{cite journal|title=A NOTE ON COMPLEXITY OF GENETIC MUTATIONS|journal=Discrete Mathematics, Algorithms and Applications|volume = 03|date = 2011|issue = 03|pages = 269-287|doi=10.1142/S1793830911001206}}</ref>：
 * {{OEIS2C|A058986}} – 最坏情况下需要翻的次数
 * {{OEIS2C|A067607}} – 有多少种煎饼长度排列是最坏情况（即上表每行最后一个数）
-* {{OEIS2C|A078941}} – maximum number of flips for a "burnt" stack
+* {{OEIS2C|A078941}} – 焦煎饼问题中最坏情况下需要翻的次数
-* {{OEIS2C|A078942}} – the number of flips for a sorted "burnt-side-on-top" stack
+* {{OEIS2C|A078942}} – 有多少种焦煎饼长度排列是最坏情况
 * {{OEIS2C|A092113}} – 即将上表每一行连接起来
 == 参考文献 ==
-{{Reflist}}
+{{Reflist|2}}
 == 拓展阅读 ==
 {{refbegin}}
-* {{cite journal|last1=Chitturi|first1=B.|last2=Sudborough|first2=H.|title=Prefix Reversals on Strings|journal=Proceedings of the International Conference on Bioinformatics & Computational Biology|volume=2|date=2010|pages=591–598|url=https://www.researchgate.net/publication/221051667_Prefix_Reversals_on_Strings}}
-* {{cite journal|last1=Chitturi|first1=B.| title=A NOTE ON COMPLEXITY OF GENETIC MUTATIONS| journal=Discrete Math. Algorithm. Appl.|volume=3|date=2011| pages= 269-287| doi=10.1142/S1793830911001206}}
 * {{cite journal|last1=Heydari|first1=M. H.|last2=Sudborough|first2=I. H.|title=On the Diameter of the Pancake Network|journal=Journal of Algorithms|date=1997|volume=25|issue=1|pages=67–94|doi=10.1006/jagm.1997.0874}}
-*{{cite journal|last1=Hurkens|first1=C.|last2=van Iersel|first2=L.|last3=Keijsper|first3=J.|last4=Kelk|first4=S.|last5=Stougie|first5=L.|last6=Tromp|first6=J.|title=Prefix Reversals on Binary and Ternary Strings|journal=SIAM Journal on Discrete Mathematics|date=2007|volume=21|issue=3|pages=592–611|doi=10.1137/060664252|arxiv=math/0602456}}
 * {{cite journal|last1=Roney-Dougal|first1=C. |last2=Vatter|first2=V.|url=http://plus.maths.org/issue54/features/colvatter/ |title=Of Pancakes, Mice and Men|journal=Plus Magazine |volume=54 |date=March 2010}}
 {{refend}}
 == 外部链接 ==
-* [http://www.cut-the-knot.org/SimpleGames/Flipper.shtml Cut-the-Knot: Flipping pancakes puzzle], including a Java applet for the pancake problem and some discussion.
+* [http://www.cut-the-knot.org/SimpleGames/Flipper.shtml Cut-the-Knot上的翻煎饼谜题]{{Wayback|url=http://www.cut-the-knot.org/SimpleGames/Flipper.shtml |date=20120414183601 }}，用[[Java]]实现的煎饼问题程序，以及一些讨论。
-* [http://www.math.uiuc.edu/~west/openp/pancake.html Douglas B. West's "The Pancake Problems"]
+* [http://www.math.uiuc.edu/~west/openp/pancake.html 道格拉斯·韦斯特讲述的煎饼问题]{{Wayback|url=http://www.math.uiuc.edu/~west/openp/pancake.html |date=20120204035551 }}
 * {{MathWorld |urlname=PancakeSorting |title=Pancake Sorting}}
-* [https://www.webcitation.org/66htQBNaj?url=http://www.bio.davidson.edu/people/kahaynes/FAMU_talk/Living_computer.swf Animation explaining the bacterial computer that can solve the burnt pancake problem.]
+* [https://web.archive.org/web/20120212231352/http://www.bio.davidson.edu/people/kahaynes/FAMU_talk/Living_computer.swf 一部小动画，演示了细菌计算机如何解决焦煎饼问题]。
-* [https://web.archive.org/web/20140607001227/http://arkaroychowdhury1.wordpress.com/2014/06/02/tower1/ "Tower1/Pancake Flip" by Arka. A game based on pancake problem principle]
 {{排序算法}}

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

查论编排序算法
理论	計算複雜性理論大O符号全序关系数据结构术语列表原地算法稳定性比较排序自适应排序（英语：Adaptive sort）排序网络（英语：Sorting network）整数排序（英语：Integer sorting） X+Y排序（英语：X + Y sorting）量子排序（英语：Quantum sort）
交换排序	冒泡排序鸡尾酒排序奇偶排序梳排序侏儒排序快速排序慢速排序臭皮匠排序 Bogo排序
选择排序	选择排序堆排序平滑排序（英语：Smoothsort）笛卡尔树排序（英语：Cartesian tree sort）锦标赛排序（英语：Tournament sort）圈排序（英语：Cycle sort）弱堆排序（英语：Weak heap）
插入排序	插入排序希尔排序伸展排序二叉查找树排序图书馆排序耐心排序
归并排序	归并排序梯级归并排序（英语：Cascade merge sort）振荡归并排序（英语：Oscillating merge sort）多相归并排序（英语：Polyphase merge sort）
分布排序	美国旗帜排序（英语：American flag sort）珠排序桶排序爆炸排序（英语：Burstsort）计数排序比較計數排序插值排序鸽巢排序相邻图排序（英语：Proxmap sort）基数排序闪电排序（英语：Flashsort）
并发排序	双调排序器（英语：Bitonic sorter） Batcher归并网络两两排序网络（英语：Pairwise sorting network）
混合排序	塊排序（英语：Block sort） Tim排序内省排序 Spread排序（英语：Spreadsort）归并插入排序（英语：Merge-insertion sort）
其他	拓撲排序煎餅排序意粉排序（英语：Spaghetti sort）