Home » Algorithms » Pancake Flipping

Pancake Flipping

Problem Description

Given a stack of n pancakes, we assign each pancake a number i, 1 \le i \le n, where the pancakes are numbered in order of increasing diameter. 1 is the smallest pancake and n is the largest. We assume that the pancakes have distinct diameters.

Our convention will be to describe a stack as a numeric list, with the leftmost element representing the current top of the stack. For example, 1 2 3 denotes a stack of pancakes already sorted according to our preference: the smallest pancake is on top, directly beneath it lies the medium-sized pancake, and the largest pancake is at the bottom. 3 2 1 is the opposite of our desired ordering: the pancakes are precariously stacked with the largest pancake on top.

Stacks of Pancakes

Our goal is to sort the pancakes such that the largest pancake is on the bottom and every pancake has only smaller pancakes stacked above it. To achieve this goal, we have in our possession a powerful spatula, with which we can flip the entire stack or any topmost subsection. Our analysis will establish an upper bound on the number of flips required to sort a stack of pancakes, given an arbitrary initial ordering.

Flipping

Establishing an Upper Bound

We will show that we can sort any stack of n pancakes in at most 2n - 5 flips.

For n = 1, the number of required flips is 0. For n = 2, the number of flips is at most 1.

Based on this, the obvious algorithm is to order pancakes 3 through n at the bottom of the stack, then use at most 1 additional flip to order the top 2 pancakes.

Sorting n Pancakes

In the for loop, the first flip brings pancake i to the top of the stack and the second flip moves pancake i to the ith position in the stack. We see that, after the loop’s first iteration, pancake n is at the bottom of the stack. The second iteration places pancake n-1 on top of pancake n. Each additional iteration orders another pancake at the bottom of the stack. Thus, in at most 2 flips each, we sort the largest n - 2 pancakes. Then, to sort pancakes 1 and 2, we need at most one more flip. The total number of flips, using the obvious algorithm, is at most 2 * (n - 2) + 1 = 2n - 3.

However, we can do better than this.

A Matlab program was written to generate all possible orderings of stacks of four pancakes, which correspond to the 24 permutations of the set \{1, 2, 3, 4\}. Then the above algorithm was run on each permutation, with the enhancement that unnecessary flips in the above routine were omitted. For example, with the permutation 2314, there is no need to waste two flips bringing 4 to the top of the stack (4132) and back to the bottom (2314). The results of the algorithm are presented in the following table:

Even using the obvious algorithm, we are able to sort almost any stack of 4 pancakes in 4 flips or less. Let us consider the two highlighted permutations which require, by the naive algorithm, 5 flips to sort. Treating these two permutations as special cases, it is possible to sort each of them in 3 flips: 3 2 4 1 \rightarrow 2 3 4 1 \rightarrow 4 3 2 1 \rightarrow 1 2 3 4 and 2 4 3 1 \rightarrow 3 4 2 1 \rightarrow 4 3 2 1 \rightarrow 1 2 3 4. Thus, by incorporating the knowledge of how best to flip these two cases, we can extend our previous algorithm to sort the first n - 4 pancakes using 2 flips each, and then sort the remaining 4 pancakes in, at most, 4 flips. This reduces our lower bound to 2n - 4. However, again we can do better.

Because it will help in the next stage of our analysis, we also note that the permutations 1243 and 1432, while requiring 4 flips by our basic algorithm, can each be sorted in 3 flips: 1243 \rightarrow 3421 \rightarrow 4 3 21 \rightarrow 1234 and 1432 \rightarrow 2341 \rightarrow 4321 \rightarrow 1234. We give the updated table below:

To further reduce our upper bound on the number of flips, we run our Matlab code on the 120 permutations of stacks of 5 pancakes. First, our basic algorithm (the psuedo-code above) is able to sort 97 of the stacks in 5 or fewer flips. This leaves us with 23 stacks that, potentially, require more than 5 flips to sort. These are presented below:

For each of the above permutations, we check to see if the number of flips required to bring pancake 5 to the bottom of the stack (which could be 0, 1, or 2 flips) plus the number of flips to sort the resulting permutation of \{1, 2, 3, 4\} (found via our table of results for n = 4) on top of the stack was less than or equal to 5. In 14 cases, it was. This left us with 9 remaining permutations of five pancakes to consider.

A combination of brute-force search and table lookups of previous values produced the following solutions for each of the above 9 permutations, all in 5 flips or less:

Using an algorithm encoded with the special cases above, we can sort any stack of 5 pancakes in at most 5 flips. Thus, we extend our original algorithm to sort a stack of n pancakes by first sorting the largest n - 5, using at most 2 flips each, followed by at most 5 flips to sort the last five pancakes. The total number of flips is less than or equal to 2 \times (n - 5) + 5 = 2n - 5 flips, establishing our proposed upper bound.

Further Reading

Pancake Sorting on Wikipedia. Interestingly, Bill Gates coauthored a research paper on this sorting problem in 1979.

Advertisements

1 Comment

  1. Saerorm Park says:

    awesome 🙂

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: