TOPICS

Pancake Sorting

Assume that numbered pancakes are stacked, and that a spatula can be used to reverse the order of the top pancakes for . Then the pancake sorting problem asks how many such "prefix reversals" are sufficient to sort an arbitrary stack (Skiena 1990, p. 48).

The maximum numbers of flips needed to sort a random stack of , 2, 3, ... pancakes are 0, 1, 3, 4, 5, 7, 8, 9, 10, 11, 13, ... (OEIS A058986), with the number of maximal stacks for , 3, ... being 1, 1, 3, 20, 2, 35, 455, ... (OEIS A067607).

The following table (OEIS A092113) gives the numbers of stacks of pancakes requiring flips. A flattened version is shown above as a binary plot.

 0 1 2 3 4 5 6 7 8 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

For example, the three stacks of four pancakes requiring the maximum of four flips are , , and , which can be ordered using the flip sequences , , and , respectively (illustrated above). Similarly, the two stacks of six pancakes requiring the maximum of seven flips are and , which can be ordered using the flip sequences and , respectively.

It is known that for , if is a multiple of 16, and .

Pancake Theorem, Tower of Hanoi

References

Berman D. and Klamkin, M. S. "A Reverse Card Shuffle." SIAM Rev. 19, 739-741, 1977.Cohen D. S. and Blum, M. "On the Problem of Sorting Burnt Pancakes." Discr. Appl. Math. 61, 105-120, 1995.Dweighter, H. "Problem E2569." Amer. Math. Monthly 82, 1010, 1975.Garey, M. R.; Johnson, D. S.; and Lin, S. Amer. Math. Monthly 84, 296, 1977.Gates, W. and Papadimitriou, C. "Bounds for Sorting by Prefix Reversal." Discr. Math. 27, 47-57, 1979.Györi, E. and Turán, G. "Stack of Pancakes." Studia Sci. Math. Hungar. 13, 133-137, 1978.Heydari M. H. and Sudborough, I. H. "On the Diameter of the Pancake Network." J. Algorithms 25, 67-94, 1997.Morales L. and Sudborough, I. H. "A Quadratic Lower Bound for Reverse Card Shuffle." Presented at 26th S.E. Conf. Comb. Graph Th. Computing. Preprint 1995.Pegg, E. Jr. "Pancake Sequence." http://www.mathpuzzle.com/pancakes.htm.Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, 1990.Sloane, N. J. A. "My Favorite Integer Sequences." In Sequences and Their Applications (Proceedings of SETA '98) (Ed. C. Ding, T. Helleseth, and H. Niederreiter). London: Springer-Verlag, pp. 103-130, 1999. http://www.research.att.com/~njas/doc/sg.pdf.Sloane, N. J. A. Sequences A058986, A067607, and A092113 in "The On-Line Encyclopedia of Integer Sequences."West, D. B. "The Pancake Problems (1975, 1979, 1973)." http://www.math.uiuc.edu/~west/openp/pancake.html.

Pancake Sorting

Cite this as:

Weisstein, Eric W. "Pancake Sorting." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/PancakeSorting.html