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.
Question 4:
(Conway - 1973; Deterministic version) If the number of elements in the
prefix reversal always equals the value of the first element, and the process
stops when element 1 is at the front, then what is the maximum number
of steps to termination?
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 23n/14 flips, and Heydari and Sudborough [HS] improved this to 3(n+1)/2. A sequence of flips that sorts a burnt permutation also sorts the corresponding ordinary permutation when sign of elements is ignored, so the sorting complexity of each unburnt permutation is bounded by the complexities of its burnt versions. Hence proving Conjecture 3 would improve the upper bound on the original Pancake Problem.
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.