Pancakes with a Problem

The cook at the Sunrise Cafe is sloppy: when she prepares pancakes, they come out all different sizes.

The waiter, however, is tidy. Before he delivers a stack to a customer, he rearranges them (so that smallest is on top, and so on down to the largest at the bottom.) He does this by grabbing several from the top and flipping them over, repeating this (varying the number he flips) as many times as necessary.

He wants to sort the pancakes as quickly as possible. How fast can he do it?

Example

Suppose a five-pancake stack starts out in the following order:

Here's one way the waiter could sort it.

1. Flip the whole stack over. This puts the largest pancake on the bottom.

2. Flip the top four pancakes.

3. Flip the top three pancakes.

4. Flip the top four pancakes.

So, we know this stack can be sorted in four steps.

Aside: Developing a Notation

Before proceeding, let's develop a notation to represent stacks: it'll make it easier to analyze and develop solutions. Plus, I don't really wanna make diagrams for every stack in this set of notes

Since every pancake has a different size, let's rank the pancakes from 1 (smallest) to n (largest). Then, we can write a stack horizontally, e.g. a sorted stack would be (1 2 3 4 5), the example above would be (5 2 3 4 1).

Bracketing. Example, continued.

We saw that (5 2 3 4 1) can be sorted in 4 flips. But this is only half of the analysis. We know how much time we need to spend in order to sort this stack, but we have no idea if this is the best way to sort the stack. This is a fairly important concept in Computer Science: bracketing. When we want to find a solution to a problem, there are two things we're interested in.

• An upper bound - how fast can we do this? Basically, finding an algorithm that solves the problem

• A lower bound - EVERY conceivable method that solves this problem must take AT LEAST this much time. As you can probably guess, lower bounds tend to be far trickier than upper bounds.

In the case of pancake flipping, we're trying to bound the number of flips.

Going back to our example: we've found a 4-flip upper bound for (5 2 3 4 1); might there exist a method to sort this in less than four flips?

Nope. Four flips are necessary. Let's determine why.

First, one interesting observation: the only way to get a pancake to the bottom is to have it at the top in a previous step (only one type of flip affects the bottom pancake, and that flip puts the top pancake down there.) This actually suggests a way to sort any stack of pancakes, but we'll get back to that later.

Now let's try making the argument. Imagine there was some method to sort (5 2 3 4 1) in 3 flips. For any such method, the first flip has to put 5 on the bottom. If it didn't, the second flip would have to put it back on the top again: it has to end up on the bottom, after all.

A 3-flip method does not have the time to touch 5 again, so we can use similar logic to argue that the second flip must bring 4 to the top. 4 has to end up in the second-to-last position, so at some point it has to be at the top. We only have three flips, though, so we have to bring it to the top now.

The third flip puts 4 in the second-to-last position. Since the stack is not sorted, there is no way to do this in three flips.

Pancake Numbers

We've proven that the optimal method for sorting (5 2 3 4 1) takes four flips. This prompts several additional questions, though. Can every stack of five pancakes be sorted in four flips? Or does there exist a 5-stack that requires at least five flips? In general, how difficult can the cook make things for the waiter?

We can look at the problem of sorting pancakes in terms of two competing conditions. The cook chooses the ''worst possible'' stack of five pancakes, and the waiter sorts the stack in the ''fewest possible'' flips. Given these constraints, how many flips does it take to sort a stack of five pancakes? We already know that at least four flips are necessary, establishing a lower limit.

There are, in fact, 120 possible arrangements, or permutations, of five pancakes.

For each stack, there is some minimum number of flips, , that sorts the stack. In the first case, no flips are necessary because the stack is already in order. The stack (2 1 3 4 5) would require only one flip, although we can take a longer, roundabout path to achieve the same result. Hence, the minimum number of flips for this permutation is 1. We already know that it takes 4 flips to sort the (5 2 3 4 1) stack. The minimum for the stack (1 3 5 2 4) is five flips.

What we are looking for is the maximum of these minima, , as we vary the permutations. In effect, we need to find the stack that is most difficult to sort. It turns out that any permutation can be done in five or fewer flips. So 5 is the answer that we are looking for. We call this number the fifth pancake number, .

Getting back to the original question: if there are pancakes, what is the maximum number of flips that we will ever need to rearrange them? In other words, we want to find (or bound) the minimum number of flips, , required in the worst case to sort a stack of pancakes.

Examples

Let's find for small values of .

If there are no pancakes in a stack, the number of flips to put it in order is 0. So, . With one pancake in the stack, the stack must already be in order, so . With two pancakes in the stack, either the stack is already in the correct order or it is upside-down. At most, one flip would be required: .

For three pancakes, the stack (1 3 2) requires three flips. Indeed, any stack of three pancakes can be sorted in three flips. The first step gets the largest pancake to the bottom, which requires as many as two flips. Then, one more flip may be required to sort the top two. Hence, .

n	0	1	2	3
	0	0	1	3

Bounding pancake numbers

Once we get to higher numbers, the number of permutations becomes far too great to examine each stack individually. Instead, let's try to find lower and upper bounds on (i.e. bracketing).

Upper bound: The "Bring-to-top" Algorithm

To find an upper bound, we want to craft an algorithm that will sort any stack of pancakes. Let's attack this recursively: if we can get the biggest pancake to the bottom, then we can ignore it and recursively deal with the top pancakes. Here's an implementation:

If the size of the stack is 1, we're done! Otherwise, flip pancake to the top, then flip it to the bottom. Repeat this algorithm on the top pancakes.

We call this the "bring-to-top" method for sorting pancakes. It lets us set an upper bound on the number of flips required to sort a stack: except for 1 each step requires two flips, so the total cost is flips.

We can slightly improve on this bound. We only need 1 flip to sort the last two pancakes, so modify the algorithm to take advantage of this.

If the size of the stack is 2, use one flip to sort the last two pancakes. Otherwise, flip pancake to the top, then flip it to the bottom. Repeat this algorithm on the top pancakes.

This improves our upper bound to .

It's important to note that the bring-to-top method is not always optimal for a particular stack. We showed earlier that the stack (5 2 3 4 1) can be sorted using four flips, but using our algorithm will take five flips..

(5 2 3 4 1)
(1 4 3 2 5)
(4 1 3 2 5)
(2 3 1 4 5)
(3 2 1 4 5)
(1 2 3 4 5)

Lower bound

Lower bounds are a lot trickier. Our previous argument was pretty specific (and pretty much used brute force) - how can we create an argument that applies to ANY algorithm we try to use...

Here's what we'll do - we'll find a really bad stack and show that this stack requires many flips. Even making this argument for a single stack can be tricky, but we can use the following observation to make things easier:

Suppose that a stack contains a pair of adjacent pancakes that will not be adjacent in the sorted stack. Any sequence of flips that sorts stack must involve one flip that inserts the spatula between the two members of this pair and breaks it apart. Furthermore, the same principle holds for the "pair" formed by the bottom pancake of and the plate.

Make sure you understand why this is true! Let's say that there was some adjacent pair in a stack that aren't consecutive numbers, e.g. (1 4). If we never make a flip between the 1 and the 4, they will always be adjacent. But we know that they aren't adjacent in the sorted stack, so we have to insert the spatula in between the two at some point.

So consider any stack where each consecutive pair is separated, e.g. (5 2 4 1 3). The above observation shows that we'll need a minimum of flips in order to sort it. This proves a lower bound on the pancake number.

Exercise

Construct a procedure that creates a permutation without adjacent pairs for any . Note that you can't do this for - hence the reason why our lower bound doesn't apply to .

Variant: From one permutation to any other

Starting with any stack, we can get to the sorted stack using no more than flips. Similarly, going from a sorted stack to any stack also requires no more than flips, just by reversing the sequence that we would use to sort the stack. Hence, going from any stack to any other stack can be done in no more than .

Is there a way to do this in faster than flips? Think about it for a second. What is the operation you're doing? What makes the sorted stack so special, if anything?

...

A hint to help solve the problem: Try proving that you can reverse sort (largest on top) it in no more than flips.

...

So the answer is yes, there is a faster way. The thing is that there's nothing special about the way we numbered the pancakes. Let's say we wanted to translate (5 2 4 3 1) to (4 3 5 1 2). Let's just renumber the pancakes: 4 becomes 1, 3 becomes 2, 5 becomes 3, 1 becomes 4, and 2 becomes 5. Now rewrite our original stack using this scheme, (3 5 1 2 4), and sort it.

This is a cool example of abstraction! You'll see more of it in lectures to come.

Pancake History

Writing under the name "Harry Dweighter" (or "Harried Waiter"), Jacob Goodman first posed the pancake problem in 1975 in the ''American Mathematical Monthly'' (vol. 82, p. 1010, 1975).

The problem attracted considerable attention in subsequent years. In general terms, it concerns the number of flips, or ''prefix reversals'', needed to sort the elements of an arbitrary permutation. Initial work on the problem established the limits (for ), as we saw above.

In 1979, William H. "Bill" Gates and Christos H. Papadimitriou improved on the upper and lower limits, showing that flips always suffice and that flips may be needed. This is the only published paper by Bill Gates, based on research conducted when he was an undergraduate at Harvard University before he went on to found Microsoft but published a few years later.

In 1997, Mohammad H. Heydari and I. Hal Sudborough improved the lower bound to and worked out the pancake numbers up to 13.

Here are the known pancake numbers.

n	1	2	3	4	5	6	7	8	9	10	11	12	13
	0	1	3	4	5	7	8	9	10	11	13	14	15

is unknown. We can readily show, however, that 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.

Application: Pancake Networks

A pancake stack is an example of a data structure. The pancake problem is relevant in the construction of networks of parallel processors, in which pancake sorting can provide an effective routing algorithm between processors.

The permutations of a pancake stack can be represented by a network (or graph) consisting of nodes and edges. The "pancake network" has nodes. We assign each node the name of one of the possible different stacks of pancakes. We then put a wire between two nodes if they are one flip apart. In other words, a link between two nodes exists if the label of one is derived from the other by a flip, or prefix reversal. A path from node to node via the network corresponds to a sequence of flips transforming stack into stack .

Examples

Network for :

Network for :

The reason this is really cool is that the pancake network is optimally reliable for its number of edges and nodes. Even if up to nodes get hit by lightning, the network remains connected (every node is accessible from every other node), despite the fact that each node only has degree .

We can also talk about the diameter of this network (the diameter of a graph is the maximum distance between any pair of nodes.) This is just equal to the number of flips necessary to sort a stack of pancakes, from our variant problem. Hence, in routing messages across such a network, the maximum delay between two nodes corresponds to the pancake number.

Other Applications

Pancake sorting and the pancake network also provide insights into evolutionary processes and the notion of mutation distance. 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 life forms that we know today. To reconstruct the history of such changes, we can compare the genomes of related species. For example, we 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.

One example of this process in action involves the relationship between the head cabbage (''Brassica oleracea capitata'') and the turnip (''Brassica rapa''). Although both species look and taste different, they share a recent common ancestor. Their gene sequences are very similar, with the main differences being simply a matter of gene order, achieved through reversals. In such an instance, analyzing the transformation from one species to another is analogous to the computer science problem: Given two permutations, find the shortest series of reversals to transform one into the other.

Analysis of genome rearrangements in molecular biology started in the 1930s with the publication of a paper presenting a rearrangement scenario with 17 inversions for a fruit fly species. The analysis of genomes evolving by inversions leads to the combinatorial problem of sorting by reversals—the pancake problem.

These examples illustrate how a simple, playful problem can lead to a host of new problems and applications at the frontiers of science.

References

H. Dweighter. ''American Mathematical Monthly'', 82 (1975), 1010.

W. H. Gates and C. H. Papadimitriou. Bounds for sorting by prefix reversal. ''Discrete Mathematics, ''27 (1979), 47-57.

M. H. Heydari and I. H. Sudborough. On the diameter of the pancake network. ''Journal of Algorithms, ''25 (1997), 67-94.