煎餅排序

煎饼排序（英語：）指的是将大小不同的一摞煎饼按大小排序的数学问题，其中煎饼铲子每次只能从任意位置铲起上方全部煎饼并翻面。“煎饼数”（英語：）是指给定煎饼的张数时，最坏情况下需要的最少翻面次数。这个问题最早由美国几何学家雅各布·E·古德曼提出。[1]它属于排序问题的变种。煎饼排序的目标和传统排序算法最小化比较次数不同，因为它每次操作只允许反转序列的前缀，所以需要最小化反转前缀次数。焦煎饼排序是煎饼排序的变种问题，每张煎饼都有一面是烤焦的，最终除了按照大小排序以外还要让所有焦面向下。

一次示例操作。上方是用煎饼铲子将顶上三张煎饼翻面，翻完以后变为下方所示的状态。在焦煎饼问题中，如果原来三张饼的焦面朝下，则翻完之后变为焦面朝上

煎饼问题

最初的煎饼问题

对于任意一叠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]

焦煎饼问题

焦煎饼问题（英語：）是煎饼问题的一种变体，其中每个煎饼有一面是焦的，排序后必须使所有煎饼焦的一面朝下。这是一类带符号的排列问题（英語：），如果某个煎饼焦的一面朝上，就在排列中给它加一个符号，最后结果必须不含符号。2008年，一组本科生对大腸桿菌，构造细菌计算机让其翻转类似焦煎饼的DNA序列，解决了一个简单的焦煎饼问题。DNA具有方向性（5'端和3'端）和顺序（啟動子和编码区）。虽然细菌对DNA翻转的处理能力较弱，但单次培养中为数众多的细菌提供了庞大的并行计算平台。當细菌帶有抗生素抗藥性時，DNA序列的排序問題即告解決。[7]

字符串中的煎饼问题

如果将煎饼摞视为一个字符串，每次翻转相当于取一段前缀并将其反转，这是一个置換操作。不过，前述讨论假定每个煎饼都是不同的，但是字符串可以包含相同字符，因此前缀反转所需次数可能会减少。赫肯斯（Hurkens）等人在2007年构造了二元和三元字符串前缀反转排序的多项式时间精确算法[8]，并证明了用最少的前缀反转次数将一个二元字符串变换为另一个二元字符串是NP困难的。池图瑞（Chitturi）等人[9]于2010年将上述结论推广到了一般字符串，证明了它是NP完全的，并给出了最少次数的上下界。池图瑞在2011年证明了带符号的字符串前缀反转排序（即字符串中的焦煎饼问题）也是NP完全的[10]。

历史 

煎饼排序问题最初由雅可比·古德曼提出，他当时用了假名“哈利·德威特”（原文“”，音近“”，即“忙亂的侍應”）。[11]

煎饼问题更多地在教育中见到，但也会在并行处理网络中用到，它的解答对应着处理器之间高效的最短路算法。[12][13]这个问题也在计算生物学中有所应用[6]。

微软公司创立者比尔·盖茨就这个问题在1979年发表过一篇题为《前缀逆转排序的边界问题》（英語：）的论文，这是他唯一广为人知的数学论文。在这篇论文中盖茨描述了一种高效的煎饼排序算法。[3]另外，《乃出個未來》的主創之一大卫·科恩研究了焦煎饼问题。[14]他们两位的合作者分别是赫里斯托斯·帕帕季米特里乌（当时在哈佛大学任职，目前在哥伦比亚大学）与曼纽尔·布卢姆（当时在加利福尼亞大學柏克萊分校任职，目前在卡内基·梅隆大学）。

之后，相关的字符串子串反转排序问题也得到了研究。不过，带符号的子串反转排序问题有平方时间的精确算法[15]，但（不带符号的）子串反转问题不存在多项式时间的精确算法，其多项式时间近似算法的近似因子下界为1.0008，上界为1.5[16]，后来找到了近似因子为1.375的多项式时间近似算法[17]。

煎饼图
煎饼图P3
煎饼图P4可以用4个P3递归地构造：给每个子图编号1、2、3、4，编号为i的子图每个顶点对应的排列为1－4除去i的全排列，末尾加上i

n-煎饼图的顶点用1到n的全排列编号，两个顶点之间有边当且仅当两个顶点对应的排列可以由前缀反转得到。它是n!个顶点的正則圖，度数为n−1。煎饼排序问题等价于求取煎饼图的直径。[18]

n-煎饼图记为Pn，可以使用n个Pn−1递归地构建：给每个子煎饼图分别编号1、2、……、n，编号为i的子图每个顶点对应的排列为1－n这n个数除去i的全排列，末尾加上i。

三阶及以上的煎饼图围长恒为6：

Pn的亏格γ(Pn)为：[19]

煎饼图有许多有趣的性质，例如对称性和上文所述的递归结构。另外，它是凱萊圖，因此也是顶点传递图。随着维度的增加，煎饼图的度数和直径都以低于对数的速度增长，因此它比超方形图等图更为稀疏。[19]人们对其在并行计算的互连网络模型的应用非常关注。[20][21][22]如果把煎饼图视为互连网络的模型，它的直径大小可以衡量通信延迟高低[23][24]。

相关整数序列 
给定一叠n个煎饼，有多少种长度排列可以在翻k次以内排好序
高度
n		k
01234567 89101112131415
1 1
2 11
3 1221
4 136113
5 1412354820
6 1520791992811332
7 163014954313571903101635
8 17422511191428110561150118520455
9 18563912278106663801593585132697793795804
10 1972575396322825106461377863919365130975681467873232
11 110908096429438912527371174766412651599810731425047191236489563546
12 11111010999883779375333973064788141419294933725211842004316933221311105006613032704167
13 11213214511455613009610305057046318403095551849922756397834751525125357218305656614586536481868748522001

在整數數列線上大全中，有一些序列与煎饼排序有关[10]：

  • A058986 – 最坏情况下需要翻的次数
  • A067607 – 有多少种煎饼长度排列是最坏情况（即上表每行最后一个数）
  • A078941 – 焦煎饼问题中最坏情况下需要翻的次数
  • A078942 – 有多少种焦煎饼长度排列是最坏情况
  • A092113 – 即将上表每一行连接起来

参考文献 
  1. Simon Singh. . The Guardian. 2013-11-14 [2018-04-07]. （原始内容存档于2017-07-30）.
  2. Fertin, G.; Labarre, A.; Rusu, I.; Tannier, E.; Vialette, S. . The MIT Press. 2009. ISBN 9780262062824.
  3. Gates, W.; Papadimitriou, C. (PDF). Discrete Mathematics. 1979, 27: 47–57 [2018-04-06]. doi:10.1016/0012-365X(79)90068-2. （原始内容 (PDF)存档于2007-06-10）.
  4. . 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. . 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. Bulteau, Laurent; Fertin, Guillaume; Rusu, Irena. . 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. . 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. . SIAM Journal on Discrete Mathematics. 2007-01, 21 (3): 592–611. arXiv:math/0602456 可免费查阅. doi:10.1137/060664252.
  9. B Chitturi, IH Sudborough. (PDF). Proceedings of the International Conference on Bioinformatics & Computational Biology. 2010, 2: 591–598. （原始内容存档 (PDF)于2018-04-07）.
  10. . Discrete Mathematics, Algorithms and Applications. 2011, 03 (03): 269–287. doi:10.1142/S1793830911001206.
  11. Dweighter, Harry, , Amer. Math. Monthly, 1975, 82: 1010, doi:10.2307/2318260
  12. Gargano, L.; Vaccaro, U.; Vozella, A. . Information Processing Letters. 1993, 45 (6): 315–320. MR 1216942. doi:10.1016/0020-0190(93)90043-9..
  13. Kaneko, K.; Peng, S. . . 2006: 254–259. ISBN 0-7695-2736-1. doi:10.1109/PDCAT.2006.56..
  14. Cohen, D.S.; Blum, M. . Discrete Applied Mathematics. 1995, 61 (2): 105. doi:10.1016/0166-218X(94)00009-3.
  15. Kaplan, H.; Shamir, R.; Tarjan, R.E. . Proc. 8th ACM-SIAM SODA. 1997: 178–187. doi:10.1137/S0097539798334207.
  16. Berman, P.; Karpinski, M. (PDF). Proc. 26th ICALP (1999) LNCS 1644 (Springer). 1999: 200–209.
  17. Berman, P.; Karpinski, M.; Hannenhalli, S. (PDF). Proc. 10th ESA (2002), LNCS 2461 (Springer). 2002: 200–210.
  18. Asai, Shogo; Kounoike, Yuusuke; Shinano, Yuji; Kaneko, Keiichi. . 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. Nguyen, Quan; Bettayeb, Said. (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. . Networks. 1993, 23 (4): 215–225. doi:10.1002/net.3230230403.
  21. Bass, D.W.; Sudborough, I.H. . 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. . 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. . Benjamin/Cummings. 1994.
  24. Quinn, M.J. second. McGraw-Hill. 1994.

拓展阅读 
  • Heydari, M. H.; Sudborough, I. H. . Journal of Algorithms. 1997, 25 (1): 67–94. doi:10.1006/jagm.1997.0874.
  • Roney-Dougal, C.; Vatter, V. . Plus Magazine. March 2010, 54.

外部链接 
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.