TOPICS
Search

Pancake Sorting


Assume that n numbered pancakes are stacked, and that a spatula can be used to reverse the order of the top k pancakes for 2<=k<=n. 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 a_n needed to sort a random stack of n=1, 2, 3, ... pancakes are 0, 1, 3, 4, 5, 7, 8, 9, 10, 11, 13, ... (OEIS A058986), with the number of maximal stacks for n=2, 3, ... being 1, 1, 3, 20, 2, 35, 455, ... (OEIS A067607).

PancakeSortingBinaryPlot

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

n\k012345678
11
211
31221
4136113
51412354820
61520791992811332
7163014954313571903101635
PancakeSorting4

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

It is known that a_n>=n+1 for n>=6, a_n>=17n/16 if n is a multiple of 16, and a_n<=(5n+5)/3.


See also

Pancake Theorem, Tower of Hanoi

Explore with Wolfram|Alpha

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.

Referenced on Wolfram|Alpha

Pancake Sorting

Cite this as:

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

Subject classifications