Pancake sorting problem

The pancake sorting problem is a problem from the area of discrete mathematics or theoretical computer science , in which the aim is clearly to sort a stack of pancakes according to size . The pile consists of pancakes of different sizes and should be sorted so that at the end the largest pancake is at the bottom, the second largest above to the smallest at the top. For this purpose, in each step a partial stack starting from the current top of the stack can be selected and reversed as a whole. What is required is the smallest number of steps of this type that are required to sort the entire stack regardless of the starting position.

The partial stack consisting of the top three pancakes is reversed.

The problem was first published in 1975 by Jacob E. Goodman under the pseudonym Harry Dweighter (resembles harried waiter , "stressed waiter") in the journal American Mathematical Monthly . Since then, a lot of serious research has been published on the subject. The problem is applied, among other things, to mutations in genetics.

Pancake numbers

The number of steps required to sort a stack of pancakes in each case is called a. The values are known for small ones , for larger ones there are estimates. Obviously , since a stack of a pancake is already sorted, and since the larger pancake starts out on top, the stack can be sorted by simply reversing it. ${\ displaystyle n}$ ${\ displaystyle P_ {n}}$ ${\ displaystyle n}$ ${\ displaystyle P_ {1} = 0}$ ${\ displaystyle P_ {2} = 1}$

A simple algorithm shows : To do this, the largest pancake is first brought to the top, then the stack is turned over so that it is at the bottom. After these two steps, the rest of the pile is sorted without paying attention to the bottom pancake, this is done in steps. So together with . ${\ displaystyle P_ {n + 1} \ leq 2 + P_ {n}}$ ${\ displaystyle P_ {n}}$ ${\ displaystyle P_ {2} = 1}$ ${\ displaystyle P_ {n} \ leq 2n-3}$

The barriers were continuously improved over time: William H. Gates (now known as Bill Gates ) and Christos Papadimitriou proved a first estimate in 1979:

{\ displaystyle P_ {n} <{\ frac {5n + 5} {3}}}

This estimate has since been improved on . Stands for a constant that is independent of, see O notation . ${\ displaystyle {\ frac {15n} {14}} + O (1) <P_ {n} <{\ frac {18n} {11}} + O (1)}$ ${\ displaystyle O (1)}$ ${\ displaystyle n}$

Pancake Numbers
(episode A058986 in OEIS )
${\ displaystyle n}$	1	2	3	4th	5	6th	7th	8th	9	10	11	12	13	14th	15th	16	17th
${\ displaystyle P_ {n}}$	0	1	3	4th	5	7th	8th	9	10	11	13	14th	15th	16	17th	18th	19th

Burnt pancake problem

One variation on the problem involves pancakes that are burned on one side. Here, too, a stack of pancakes should be sorted by size by reversing partial stacks, but it is also required that at the end the burned sides all face down. For the number of steps required in this variant, David S. Cohen (today David X. Cohen ) and Manuel Blum were able to prove the following estimate in 1995 : (whereby the upper bound only applies to). ${\ displaystyle 3n / 2 \ leq P '_ {n} \ leq 2n-2}$ ${\ displaystyle n> 9}$

Burned pancake numbers
(episode A078941 in OEIS )
${\ displaystyle n}$	1	2	3	4th	5	6th	7th	8th	9	10	11	12
${\ displaystyle P '_ {n}}$	1	4th	6th	8th	10	12	14th	15th	17th	18th	19th	21st

Web links

Eric W. Weisstein : Pancake Sorting . In: MathWorld (English).
Katie Steckles on Pancake Numbers . Numberphile video on YouTube

Individual evidence

↑ Brian Hayes: Genes and Pancakes. In: Spectrum of Science , October 2008. ( Spektrum.de )
^ William H. Gates, Christos Papadimitriou: Bounds for Sorting by Prefix Reversal. In: Discrete Mathematics , Vol. 27, 1979, pp. 47-57. doi: 10.1016 / 0012-365X (79) 90068-2 ; cs.berkeley.edu (PDF)
↑ B. Chitturi, W. Fahle, Z. Meng, L. Morales, CO Shields, IH Sudborough, W. Voit: An upper bound for sorting by prefix reversals. In: Theoretical Computer Science. 410, No. 36, 2009, pp. 3372-3390. doi: 10.1016 / j.tcs.2008.04.045 .
^ David S. Cohen, Manuel Blum: On the problem of sorting burnt pancakes. In: Discrete Applied Mathematics , 61, No. 2, 1995, pp. 105-120, doi: 10.1016 / 0166-218X (94) 00009-3 .

[1] Brian Hayes: Genes and Pancakes. In: Spectrum of Science , October 2008. ( Spektrum.de )

[2] William H. Gates, Christos Papadimitriou: Bounds for Sorting by Prefix Reversal. In: Discrete Mathematics , Vol. 27, 1979, pp. 47-57. doi: 10.1016 / 0012-365X (79) 90068-2 ; cs.berkeley.edu (PDF)

[3] B. Chitturi, W. Fahle, Z. Meng, L. Morales, CO Shields, IH Sudborough, W. Voit: An upper bound for sorting by prefix reversals. In: Theoretical Computer Science. 410, No. 36, 2009, pp. 3372-3390. doi: 10.1016 / j.tcs.2008.04.045 .

[4] David S. Cohen, Manuel Blum: On the problem of sorting burnt pancakes. In: Discrete Applied Mathematics , 61, No. 2, 1995, pp. 105-120, doi: 10.1016 / 0166-218X (94) 00009-3 .