How do you solve the pancake problem?

Answer

There is, however, a solution method described in the Dutch Wikipedia about Pancake sort (under the heading Algorithm). The idea is to always get the biggest one in the back. You can do this by flipping right after him so that he’s in the front, and then flipping the whole thing so he’s in the back. From then on you just leave the biggest one behind and you repeat the algorithm on the remaining numbers. An example:

Given the sequence (3,2,4,5,1).

1.a. Flip after largest: (5,4,2,3,1)

1.b. Flip the whole: (1,3,2,4,5)

2. The biggest one is already at the back. From now on, we’ll leave it alone and repeat the algorithm with the remaining numbers. Now in this example, the second largest is also at the back, so we don’t have to do anything more for that. There are now three numbers left.

3.a. Flip after third largest: (3,1,2,4,5)

3.b. Flip the whole (only 3 numbers): (2,1,3,4,5)

4. The fourth largest is already in front, so we just need to flip the remaining 2 numbers: (1,2,3,4,5)

Finished.

Another example in the row (4,8,2,3,7,6,1,5):

– (8.4,2.3,7,6,1.5)

– (5,1,6,7,3,2,4,8)

– (7,6,1,5,3,2,4,8)

– (4,2,3,5,1,6,7,8)

– (5.3,2,4,1,6,7,8)

– (1,4,2,3,5,6,7,8)

– (4,1,2,3,5,6,7,8)

– (3,2,1,4,5,6,7,8)

– (1,2,3,4,5,6,7,8)

This method is the simplest and there are smarter methods that require fewer steps.