Pancake sorting

Pancake sorting 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 geometer 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 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.

The pancake problems

The original pancake problem

The minimum number of flips required to sort any stack of n pancakes has been shown to lie between 15/14n and 18/11n, but the exact value is not known.[2]

The simplest pancake sorting algorithm requires at most 2n − 3 flips. In this algorithm, a variation of selection sort, we bring the largest pancake not yet sorted to the top with one flip, and then take it down to its final position with one more, then repeat this for the remaining pancakes.

In 1979, Bill Gates and Christos Papadimitriou[3] gave an upper bound of 5/3n. This was improved, thirty years later, to 18/11n by a team of researchers at the University of Texas at Dallas, led by Founders Professor Hal Sudborough[4] (Chitturi et al., 2009).

The problem of determining the minimal number of moves for a given stack has been shown to be NP-hard in a paper published in 2015,[5] thereby answering a question open for over three decades.

The burnt pancake problem

In a more difficult 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. 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.[6]

The pancake problem on strings

The above discussion presumes that each pancake is unique, i.e. the sequence on which the prefix reversals are performed is a permutation. However, "strings" are sequences in which a symbol can repeat. Chitturi and Sudborough (2010) and Hurkens et al. (2007) independently showed that the complexity of transforming a compatible string into another with prefix reversals is NP-complete. They also gave bounds for the same. Hurkens et al. gave an exact algorithm to sort binary and ternary strings. Chitturi (2011) proved that the complexity of transforming a compatible signed string into another with prefix reversals, i.e. the burnt pancake problem on strings, is NP-complete.

History

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.[7][8]

The problem is notable as the topic of the only well-known mathematics paper ever written by Microsoft founder Bill Gates (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 Futurama co-creator David X. Cohen (as David S. Cohen) concerned the burnt pancake problem.[9] Their collaborators were Christos Papadimitriou (then at Harvard, now at Berkeley) and Manuel Blum (then at Berkeley, now at Carnegie Mellon University), 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,[10] the problem of sorting by reversals has been proven to be hard even to approximate to within certain constant factor,[11] and also proven to be approximable in polynomial time to within the approximation factor 1.375.[12]

Related integer sequences

Number of stacks of given height n that require k flips 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 Neil Sloane:

References

  1. ↑ Simon Singh (November 14, 2013). "Flipping pancakes with mathematics". The Guardian. Retrieved March 25, 2014.
  2. ↑ Fertin, G. and Labarre, A. and Rusu, I. and Tannier, E. and Vialette, S. (2009). Combinatorics of Genome Rearrangements. The MIT Press. ISBN 9780262062824.
  3. 1 2 Gates, W.; Papadimitriou, C. (1979). "Bounds for Sorting by Prefix Reversal" (PDF). Discrete Mathematics 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. Retrieved 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. ↑ Bulteau, Laurent; Fertin, Guillaume; Rusu, Irena. "Pancake Flipping Is Hard". Journal of Computer and System Sciences 81 (8): 1556–1574. doi:10.1016/j.jcss.2015.02.003.
  6. ↑ 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 (2008). "Engineering bacteria to solve the Burnt Pancake Problem". Journal of Biological Engineering 2: 8. doi:10.1186/1754-1611-2-8. PMC 2427008. PMID 18492232.
  7. ↑ Gargano, L.; Vaccaro, U.; Vozella, A. (1993). "Fault tolerant routing in the star and pancake interconnection networks". Information Processing Letters 45 (6): 315–320. doi:10.1016/0020-0190(93)90043-9. MR 1216942.
  8. ↑ Kaneko, K.; Peng, S. (2006). "Disjoint paths routing in pancake graphs". Proceedings of Seventh International Conference on Parallel and Distributed Computing, Applications and Technologies, 2006 (PDCAT '06). pp. 254–259. doi:10.1109/PDCAT.2006.56. ISBN 0-7695-2736-1.
  9. ↑ Cohen D.S.; Blum, M. (1995). "On the problem of sorting burnt pancakes". Discrete Applied Mathematics 61 (2): 105. doi:10.1016/0166-218X(94)00009-3.
  10. ↑ Kaplan, H., Shamir, R. and Tarjan, R.E. "Faster and Simpler Algorithm for Sorting Signed Permutations by Reversals." Proc. 8th ACM-SIAM SODA (1997), 178-187, 1997.
  11. ↑ Berman, P. and Karpinski, M. "On Some Tighter Inapproximability Results." Proc. 26th ICALP (1999), LNCS 1644, Springer, 200-209, 1999.
  12. ↑ Berman, P., Karpinski M. and Hannenhalli, S., "1.375-Approximation Algorithms for Sorting by Reversals." Proc. 10th ESA (2002), LNCS 2461, Springer, 200-210, 2002.

Further reading

External links

This article is issued from Wikipedia - version of the Saturday, December 19, 2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.