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. The
pancake sorting
problem
asks how many such "
prefix reversals" are sufficient to sort an arbitrary
stack.
For example, consider the stack:
(top) 5 3 1 4 2 (bottom)
The Pancake Sorting problem is to get this into
(top) 1 2 3 4 5 (bottom)
Thus...
flip(5) -> (top) 2 4 1 3 5 (bottom)
flip(2) -> (top) 4 2 1 3 5 (bottom)
flip(4) -> (top) 3 1 2 4 5 (bottom)
flip(3) -> (top) 2 1 3 4 5 (bottom)
flip(2) -> (top) 1 2 3 4 5 (bottom)
Voila... now where is the maple syrup?