**Originator(s):**
Jacob Goodman, Bill Gates & Christos Papadimitriou, John Conway

**Definitions:**
A *prefix* of a permutation or string is an initial segment.
A *flip* is the reversal of a prefix. In a *signed permutation*,
each element *i* occurs as *i* or *i'*, and *i'* is treated
as a negated element. When reversing a prefix of a signed permutation, the
signs also reverse.

**Question 1:**
(Goodman - 1975) What is the maximum number of flips needed to sort a permutation of
*[n]* into ascending order?
**Question 2:**
(Gates and Papadimitriou - 1979)
What is the maximum number of flips needed to sort a signed permutation of
*[n]* into ascending order with all positive signs?
**Conjecture 3:**
The signed permutation of *[n]* that needs the most flips to sort is
*1'2'...n'*, called *I' _{n}*.

**Background/motivation:**
Writing under the name ``Harry Dweighter'', Jacob Goodman [D] described a
waiter navigating a busy restaurant with a stack of *n* pancakes. To
avoid disaster, the waiter wants to sort the pancakes in order by size.
Having only one free hand, the only available operation is to lift a top
portion of the stack, invert it, and replace it. Finding the maximum number of
flips needed is the *Pancake Problem*.

Gates and Papadimitriou [GP] introduced the *Burnt Pancake Problem*.
here one side of each pancake is burnt, and the pancakes must be sorted
with the burnt side down. We represent the condition that pancake *i* is
"burnt side up" by putting a negative element *i'* in place of *i* in
the permutation.

The pancake problem relates to the construction of networks of parallel
processors. The network defined by prefix reversal has sublogarithmic
diameter and degree as a function of the number of vertices (*n!*). For
the hypercube these values are logarithmic. The transposition network on
permutations has slighlty smaller diameter than the pancake network (*n*
instead of something between *15n/14* and *5n/3*), but its degree is
quadratic instead of linear in *n*. A prefix reversal sorting algorithm
provides a routing algorithm in the network. [19] contains further discussion
of the applications.

Conway called the process in the deterministic problem "topswaps".
Knuth observed that the Fibonacci numbers provide an upper bound and posed that
as an examination question in 1974. Berman and Klamkin [BK] called the problem
"Reverse Card Shuffle" and conjectured that the permutation with the maximimum
number of steps to termination arrives at the identity permutation. This fails
for *n=12* and *n=15* [MS].

**Comments/Partial results:**
For the Pancake Problem, an upper bound of *2n-3* arises by iteratively
putting the next largest element in its proper place with two flips. When
the initial permutation has none of the desired adjacencies, at least *n*
flips are needed. Gates and Papadimitriou [GP] showed that *(5n+5)/3*
flips always suffice and that *17n/16* flips may be needed. Heydari and
Sudborough [HS] improved the lower bound to *15n/14*. They present the
exact values up through *n=13*, where 15 flips is the maximum.

For the Burnt Pancake Problem, the lower and upper bounds provided by Gates and
Papadimitriou were improved slightly by Cohen and Blum [CB] to *3n/2* and
*2n-2*. Cohen and Blum proved that *I' _{n}* can be sorted in

For the deterministic problem, Knuth's upper bound using Fibonacci numbers
grows exponentially with *n*. Knuth conjectured that the maximum length
to termination has a linear upper bound. This was disproved by Morales and
Sudborough [MS], who constructed permutations that take a quadratic number of
steps to termination.

For known values on these problems, see [O].

**References:**

[BK] Berman D.; Klamkin, M.S. A reverse card shuffle,
SIAM Review 19 (1977), 739--741.

[CB] Cohen D.S.; Blum, M. On the problem of sorting burnt pancakes.
Discrete Appl. Math. 61 (1995), no. 2, 105--120.

[D] Dweighter, Harry. American Mathematical Monthly 82(1975), 1010.

[GP] Gates W.H.; Papadimitriou, C.H. Bounds for sorting by prefix reversal.
Discrete Math. 27 (1979), 47--57.

[HS] Heydari M.H.; Sudborough, I.H. On the diameter of the pancake network.
J. Algorithms 25 (1997), no. 1, 67--94.

[MS] Morales L.; Sudborough, I.H. A quadratic lower bound for reverse card
shuffle. at 26th S.E. Conf. Comb. Graph Th. Computing, preprint 1995.

[O] OEIS, Sequences A058986,
A078941,
A078942, etc.