Pancake sorting is the problem of sorting a stack of distinctly numbered pancakes using reversals of the top pancakes, where and is a positive integer.
It asks for the minimum number of these prefix reversals
needed to sort an arbitrary stack (Skiena 1990, p. 48).
The worst-case minimum numbers of flips , taken over all stacks 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 (Gates and Papadimitriou 1979, West).
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. Monthly82, 1010, 1975.Garey, M. R.;
Johnson, D. S.; and Lin, S. Amer. Math. Monthly84, 296, 1977.Gates,
W. and Papadimitriou, C. "Bounds for Sorting by Prefix Reversal." Disc.
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. Algorithms25, 67-94, 1997.Morales,
L. and Sudborough, I. H. "A Quadratic Lower Bound for Topswops." Theoret.
Comput. Sci.411, 3965-3970, 2010. https://doi.org/10.1016/j.tcs.2010.08.011.Numberphile.
"Pancake Numbers." Oct. 27, 2017. https://www.youtube.com/watch?v=m3drS_8BpU0.Pegg,
E. Jr. "MathPuzzle: Pancake Sequence." Jan. 27, 2003. https://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,
England: Springer-Verlag, pp. 103-130, 1999. https://neilsloane.com/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)." https://dwest.web.illinois.edu/openp/pancake.html.
distinctly numbered pancakes using reversals of the top 
pancakes, where 
and 
is a positive integer.
It asks for the minimum number of these prefix reversals
needed to sort an arbitrary stack (Skiena 1990, p. 48).
, taken over all stacks 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).
pancakes requiring 
flips. A flattened version is shown above as a binary
plot.
,
, 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.
for 
,
if 
is a multiple of 16, and 
(Gates and Papadimitriou 1979, West).
