Pancake sorting

The pancake sorting problem is a problem in the field of discrete mathematics and theoretical computer science, which is vividly comes to sort a stack of pancakes by size. The stack consists of pancakes of different sizes and should be sorted so that at the end of the largest pancake is at the lowest position, the second largest to the smallest over the top. For this purpose, an outgoing from the current top of the stack stack portion may be reproduced in any step be selected and vice versa as a whole. What is required is for the smallest number of steps of this type, which are required to sort, regardless of the initial position of the entire stack.

The problem in 1975 by Jacob E. Goodman under the pseudonym Harry Dweighter was first published (pronounced as harried waiter, so tormented upper ) in the journal American Mathematical Monthly. Since then, numerous serious research results have been published on the subject. Application is the problem among others mutations in genetics.

Pancake numbers

The number of steps required to sort a stack of pancakes in each case, as indicated. The values ​​are known for small, for larger, there are estimates. Obviously applies as a stack of a pancake is already sorted, and, as in the case that the greater pancakes located at the beginning above, the stack may be sorted, characterized in that it is simply reversed.

A simple algorithm is: given the largest pancake is first brought to the top, then the stack is turned over, that he is at the bottom. After these two steps, the rest of the stack is sorted, ignoring the lowest pancakes, this is done in steps. Together with valid so.

The barriers have been continuously improved over time: A first assessment proved William H. Gates (now known as Bill Gates ) and Christos Papadimitriou in 1979:

This estimate has since been improved on.

Burnt Pancake Problem

A variant of the problem is of pancakes that are burned on one side. Again, a stack of pancakes to be sorted by reversing partial stacks according to size, however, is additionally required that at the end of the burned pages show all down. For the number of steps in this variant could and Manuel Blum prove the following estimate 1995 David S. Cohen ( David X. Cohen today ): (where the upper bound only applies ).