煎餅排序：修订间差异

维基百科，自由的百科全书
下一版本→
删除的内容 添加的内容
可视化wikitext
新条目
（没有差异）

2018年4月6日 (五) 04:00的版本

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.

煎饼排序 is the colloquial term for the mathematical problem of sorting a disordered stack of pancakes in order of size when a 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 几何学家列表 Jacob E. Goodman（英语：Jacob E. Goodman）.[1] It is a variation of the sorting problem in which the only allowed operation is to reverse the elements of some prefix（英语：prefix (computer science)） 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.

煎饼问题

最初的煎饼问题

对于任意一叠n张煎饼，人们已经证明最小翻转次数在15/14n到18/11n之间（约为1.07n到1.64n之间），但精确值仍未知[2]。

最简单的算法在最坏情况下需要2n − 3次翻转。这种算法是选择排序的变体，每轮用一次翻转把未排序的煎饼中最大者翻到顶上，再用一次翻转把它翻到最终所在处（目前未排序煎饼和已排序煎饼的交界处），然后对剩余未排序煎饼重复此过程。剩下两个煎饼时只需一次翻转即完成排序。

1979年比尔·盖茨和赫里斯托斯·帕帕季米特里乌[3]给出了一个上界(5n+5)/3。三十年后德克薩斯州大學達拉斯分校Hal Sudborough教授领导的一组研究者将这个上界改进为18/11n[4][5]。

2011年，Laurent Bulteau、Guillaume Fertin和Irena Rusu[6]证明了给定一叠煎饼的长度分布，找到最短解法是NP困难的，最终解决了这个已提出三十余年的问题。

The burnt pancake problem

In a variation called the burnt pancake problem, the bottom of each pancake in the pile is burnt, and the sort must be completed with the burnt side of every pancake down. It is a signed permutation, and if a pancake i is "burnt side up" a negative element i` is put in place of i in the permutation. In 2008, a group of undergraduates built a bacterial computer that can solve a simple example of the burnt pancake problem by programming E. coli to flip segments of DNA which are analogous to burnt pancakes. DNA has an orientation (5' and 3') and an order (promoter before coding). Even though the processing power expressed by DNA flips is low, the high number of bacteria in a culture provides a large parallel computing platform. The bacteria report when they have solved the problem by becoming antibiotic resistant.[7]

The identical pancakes stack problem

This is inspired from the way Indian bread (Roti（英语：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.[8]

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困难. They also gave bounds for the same. Hurkens et al. gave an exact algorithm to sort binary and ternary strings. Chitturi[9] (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 Jacob E. Goodman（英语：Jacob E. Goodman）, writing under the pseudonym "Harry Dweighter" (harried waiter).[10]

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.[11][12]

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.[3] In addition, the most notable paper published by 乃出個未來 co-creator David X. Cohen（英语：David X. Cohen） (as David S. Cohen) concerned the burnt pancake problem.[13] Their collaborators were 赫里斯托斯·帕帕季米特里乌 (then at Harvard, now at Columbia) and 曼纽尔·布卢姆 (then at Berkeley, now at 卡内基·梅隆大学), respectively.

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,[14] the problem of sorting by reversals has been proven to be hard even to approximate to within certain constant factor,[15] and also proven to be approximable in polynomial time to within the approximation factor 1.375.[16]

煎饼图

The pancake graph P3
The pancake graph P4 can be constructed recursively from 4 copies of P3 by assigning a different element from the set {1, 2, 3, 4} as a suffix to each copy.
主条目：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−1. The pancake sorting problem and the problem to obtain the diameter（英语：Distance (graph theory)） of the pancake graph is equivalent.[17]

The pancake graph of dimension n, Pn can be constructed recursively from n copies of Pn−1, by assigning a different element from the set {1, 2, …, n} as a suffix to each copy.

Their girth:

.

The γ(Pn) genus of Pn is[18]:

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[19][20][21]. 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[22][23].

The pancake graphs are 凱萊圖s (thus are vertex-transitive（英语：Vertex-transitive graph）) and are especially attractive for parallel processing. They have sublogarithmic degree and diameter, and are relatively sparse（英语：Dense graph） (compared to e.g. hypercubes（英语：Hypercube graph）)[18].

Related integer sequences

Number of stacks of given height n that require unique flips k  to get sorted
Height
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

Sequences from The Online Encyclopedia of Integer Sequences of 尼爾·斯洛恩:

  • A058986 – maximum number of flips
  • A067607 – number of stacks requiring the maximum number of flips (above)
  • A078941 – maximum number of flips for a "burnt" stack
  • A078942 – the number of flips for a sorted "burnt-side-on-top" stack
  • A092113 – the above triangle, read by rows

[9]

参考文献 

  1. ^ Simon Singh. Flipping pancakes with mathematics. [[衛報|]]. November 14, 2013 [March 25, 2014]. 
  2. ^ Fertin, G.; Labarre, A.; Rusu, I.; Tannier, E.; Vialette, S. Combinatorics of Genome Rearrangements. The MIT Press. 2009. ISBN 9780262062824. 
  3. ^ 3.0 3.1 Gates, W.; Papadimitriou, C. Bounds for Sorting by Prefix Reversal (PDF). Discrete Mathematics（英语：Discrete Mathematics (journal)）. 1979, 27: 47–57. doi:10.1016/0012-365X(79)90068-2. 
  4. ^ Team Bests Young Bill Gates With Improved Answer to So-Called Pancake Problem in Mathematics. University of Texas at Dallas News Center. September 17, 2008 [November 10, 2008]. 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. doi:10.1016/j.tcs.2008.04.045. 
  6. ^ 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. ^ Roychowdhury, Arka. Itunes: Flipping Pancakes. Crazy1S. 
  9. ^ 9.0 9.1 A NOTE ON COMPLEXITY OF GENETIC MUTATIONS. Discrete Mathematics, Algorithms and Applications. doi:10.1142/S1793830911001206. 
  10. ^ Dweighter, Harry, Elementary Problem E2569, Amer. Math. Monthly, 1975, 82: 1010, doi:10.2307/2318260 
  11. ^ 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-9Template:Inconsistent citations .
  12. ^ 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.56Template:Inconsistent citations .
  13. ^ 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. 
  14. ^ Kaplan, H.; Shamir, R.; Tarjan, R.E. Faster and Simpler Algorithm for Sorting Signed Permutations by Reversals. Proc. 8th ACM-SIAM SODA. 1997: 178–87. 
  15. ^ Berman, P.; Karpinski, M. On Some Tighter Inapproximability Results.. Proc. 26th ICALP (1999) LNCS 1644 (Springer). 1999: 200–09. 
  16. ^ Berman, P.; Karpinski, M.; Hannenhalli, S. 1.375-Approximation Algorithms for Sorting by Reversals.. Proc. 10th ESA (2002), LNCS 2461 (Springer). 2002: 200–10. 
  17. ^ 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. doi:10.1007/11823285_117. 
  18. ^ 18.0 18.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. 
  19. ^ 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. 
  20. ^ 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. 
  21. ^ 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. 
  22. ^ Kumar, V.; Grama, A.; Gupta, A.; Karypis, G. Introduction to Parallel Computing: Design and Analysis of Algorithms. Benjamin/Cummings. 1994. 
  23. ^ Quinn, M.J. Parallel Computing: Theory and Practice second. McGraw-Hill. 1994. 

拓展阅读 

  • Chitturi, B.; Sudborough, H. Prefix Reversals on Strings. Proceedings of the International Conference on Bioinformatics & Computational Biology. 2010, 2: 591–598. 
  • Chitturi, B. A NOTE ON COMPLEXITY OF GENETIC MUTATIONS. Discrete Math. Algorithm. Appl. 2011, 3: 269–287. doi:10.1142/S1793830911001206. 
  • 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. 
  • Hurkens, C.; van Iersel, L.; Keijsper, J.; Kelk, S.; Stougie, L.; Tromp, J. Prefix Reversals on Binary and Ternary Strings. SIAM Journal on Discrete Mathematics. 2007, 21 (3): 592–611. arXiv:math/0602456 可免费查阅. doi:10.1137/060664252. 
  • Roney-Dougal, C.; Vatter, V. Of Pancakes, Mice and Men. Plus Magazine. March 2010, 54. 

外部链接 

理论
交换排序
选择排序
插入排序
归并排序
分布排序
并发排序
混合排序
其他
取自“https://zh.wikipedia.org/w/index.php?title=煎餅排序&oldid=48994770”