Enlarge

A spatula flips over the top three pancakes in this six-pancake stack.Wikipedia

The cook at the Sunrise Cafe is sloppy. When she prepares pancakes, they all come out a different size. The server, however, is tidy. Before he delivers a stack to a customer, he rearranges the pancakes in order of size, with the smallest one on top and the largest on the bottom. To do so, he grabs several pancakes from the top and flips them over. He repeats this "grab-and-flip" operation as many times as necessary, varying the number of pancakes that he flips each time. If he has a stack of n pancakes, what's the maximum number of flips that he'll ever need to use to rearrange them?

The original pancake problem was posed in 1975 in the American Mathematical Monthly by Jacob E. Goodman, writing under the name "Harry Dweighter" (or "Harried Waiter"). It attracted considerable attention in subsequent years and has since become a staple of theoretical computer science courses.

Suppose, for example, that you have a five-pancake stack, with the pancakes ranked according to size, from 1 (smallest) to 5 (largest). The stack starts out in the following order (from top to bottom): [5 2 3 4 1]. How many flips do you need to sort this stack using the server's "grab-and-flip" sorting method?

Here's one way to do it. Flip the whole stack over. This puts the largest pancake on the bottom. Flip the top four pancakes. Flip the top three pancakes. Flip the top four pancakes. You're done in four steps.

It turns out that, given all possible arrangements of five pancakes in a stack, no more than five flips are ever needed to put a five-pancake stack in order. In fact, of the 120 possible arrangements, or permutations, of 5 pancakes, precisely 20 require the full five flips to get them into order.

The maximum number of flips ever needed to rearrange a stack of n pancakes is now known as the nth pancake number, P_n. In technical terms, the problem concerns the number of flips, or prefix reversals, needed to sort the elements of an arbitrary permutation.

Initial work established that P_n had to be at least n and no more than 2n – 3, for n greater than 2.

You can achieve the upper bound by following a simple procedure. Bring the largest pancake not yet sorted to the top with one flip. Then move it to its final position with an additional flip. Then repeat the procedure for the remaining pancakes. When you are left with just two pancakes to be sorted, the final step requires only a single flip.

In 1979, William "Bill" H. Gates and Christos H. Papadimitriou used a different sorting algorithm to improve on the upper and lower limits, showing that (5n + 5)/3 flips always suffice and that 17n/16 flips may be needed. It's the only technical paper that Bill Gates, co-founder of Microsoft, ever published. The same upper bound was independently obtained by E. Györi and G. Turán at roughly the same time.

In 1997, Mohammad H. Heydari and I. Hal Sudborough improved the lower bound to 15n/14 and computed the pancake numbers up to 13.

Here are the known pancake numbers.

P₁₄ is unknown. We can readily show, however, that P₁₄ must be at least 15 and no more than 17. In a stack of 14 pancakes, it takes at most two flips to bring the largest pancake to the bottom. That leaves an unordered stack of 13 pancakes, which we know can be sorted in no more than 15 steps.

An interesting variant of the problem, introduced by Gates and Papadimitriou, concerns pancakes that are burnt on one side. Here, the pancakes must be sorted with the burnt side down.

In general, a pancake stack is an example of a data structure, and the pancake problem is relevant, for example, to the construction of networks of parallel processors, in which pancake sorting can provide an effective routing algorithm between processors.

Pancake sorting also provides insights into evolutionary processes. In any evolutionary process, changes in DNA sequences (genomes) can cause a new species to split off from an existing one, thus leading to the diversity of lifeforms that we know today.

To reconstruct such changes, you can compare the genomes of related species. For example, you can look for reversal events, when a portion of a chromosome is deleted and replaced with the reversed sequence. Such events can create entirely new genes—and new species.

Analyzing the transformation from one species to another is analogous to the problem of finding the shortest series of reversals to transform one into the other. The analysis of genomes evolving by inversions leads to the combinatorial problem of sorting by reversals—the pancake problem.

• Print
• |
• Comment
• |
• |
• |
• Tweet
• |