Pfannkuchen-Sortierproblem

Das Pfannkuchen-Sortierproblem ist ein Problem aus dem Bereich der diskreten Mathematik bzw. der theoretischen Informatik, bei dem es anschaulich darum geht, einen Stapel Pfannkuchen der Größe nach zu sortieren. Der Stapel besteht aus Pfannkuchen unterschiedlicher Größe und soll so sortiert werden, dass am Ende der größte Pfannkuchen an unterster Stelle ist, der zweitgrößte darüber bis zum kleinsten ganz oben. Dazu darf in jedem Schritt ein von der aktuellen Spitze des Stapels ausgehender Teilstapel ausgewählt und als ganzer umgekehrt werden. Gefragt ist nach der kleinsten Anzahl an Schritten dieser Art, die benötigt werden, um unabhängig von der Ausgangslage den gesamten Stapel zu sortieren.

Erstmals veröffentlicht wurde das Problem 1975 von Jacob E. Goodman unter dem Pseudonym Harry Dweighter (gleicht in der Aussprache harried waiter, „gestresster Kellner“) in der Zeitschrift American Mathematical Monthly. Seitdem wurden zahlreiche ernsthafte Forschungsergebnisse zum Thema veröffentlicht. Anwendung findet das Problem unter anderem bei Mutationen in der Genetik.^[1]

Pfannkuchen-Zahlen

Die Anzahl der nötigen Schritte, um einen Stapel aus $n$ Pfannkuchen in jedem Fall zu sortieren, wird als $P_{n}$ bezeichnet. Die Werte sind für kleine $n$ bekannt, für größere gibt es Abschätzungen. Offensichtlich gilt $P_{1}=0$ , da ein Stapel aus einem Pfannkuchen bereits sortiert ist, und $P_{2}=1$ , da im Fall, dass der größere Pfannkuchen zu Beginn oben liegt, der Stapel dadurch sortiert werden kann, dass er einfach umgekehrt wird.

Ein einfacher Algorithmus zeigt $P_{n+1}\leq 2+P_{n}$ : Dazu wird der größte Pfannkuchen zunächst an die Spitze gebracht, anschließend wird der Stapel umgewendet, dass er sich ganz unten befindet. Nach diesen zwei Schritten wird der restliche Stapel sortiert, ohne den untersten Pfannkuchen zu beachten, dies geschieht in $P_{n}$ Schritten. Zusammen mit $P_{2}=1$ gilt also $P_{n}\leq 2n-3$ .

Die Schranken wurden im Laufe der Zeit immer weiter verbessert: Eine erste Abschätzung bewiesen William H. Gates (heute bekannt als Bill Gates) und Christos Papadimitriou im Jahr 1979:^[2]

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

Diese Abschätzung wurde inzwischen verbessert auf ${\tfrac {15n}{14}}+O(1)<P_{n}<{\tfrac {18n}{11}}+O(1)$ .^[3] Dabei steht $O(1)$ für eine von $n$ unabhängige Konstante, siehe O-Notation.

Pfannkuchen-Zahlen
(Folge A058986 in OEIS)
$n$	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17
$P_{n}$	0	1	3	4	5	7	8	9	10	11	13	14	15	16	17	18	19

Verbrannte-Pfannkuchen-Problem

Eine Variante des Problems handelt von Pfannkuchen, die auf einer Seite verbrannt sind. Auch hier soll ein Stapel Pfannkuchen durch Umkehren von Teilstapeln der Größe nach sortiert werden, allerdings wird zusätzlich gefordert, dass am Ende die verbrannten Seiten alle nach unten zeigen. Für die Anzahl der notwendigen Schritte in dieser Variante konnten 1995 David S. Cohen (heute David X. Cohen) und Manuel Blum die folgende Abschätzung beweisen: $3n/2\leq P'_{n}\leq 2n-2$ (wobei die obere Schranke nur für $n>9$ gilt).^[4]

Verbrannte-Pfannkuchen-Zahlen
(Folge A078941 in OEIS)
$n$	1	2	3	4	5	6	7	8	9	10	11	12
$P'_{n}$	1	4	6	8	10	12	14	15	17	18	19	21

Weblinks

Eric W. Weisstein: Pancake Sorting. In: MathWorld (englisch).
Katie Steckles on Pancake Numbers. Numberphile-Video bei YouTube

Einzelnachweise

↑ Brian Hayes: Gene und Pfannkuchen. In: Spektrum der Wissenschaft, Oktober 2008. (spektrum.de)
↑ William H. Gates, Christos Papadimitriou: Bounds for Sorting by Prefix Reversal. In: Discrete Mathematics, Vol. 27, 1979, S. 47–57. doi:10.1016/0012-365X(79)90068-2; cs.berkeley.edu (Memento vom 10. Juni 2007 im Internet Archive) (PDF)
↑ B. Chitturi, W. Fahle, Z. Meng, L. Morales, C. O. Shields, I. H. Sudborough, W. Voit: An upper bound for sorting by prefix reversals. In: Theoretical Computer Science. 410, Nr. 36, 2009, S. 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, Nr. 2, 1995, S. 105–120, doi:10.1016/0166-218X(94)00009-3.

[1] Brian Hayes: Gene und Pfannkuchen. In: Spektrum der Wissenschaft, Oktober 2008. (spektrum.de)

[2] William H. Gates, Christos Papadimitriou: Bounds for Sorting by Prefix Reversal. In: Discrete Mathematics, Vol. 27, 1979, S. 47–57. doi:10.1016/0012-365X(79)90068-2; cs.berkeley.edu (Memento vom 10. Juni 2007 im Internet Archive) (PDF)

[3] B. Chitturi, W. Fahle, Z. Meng, L. Morales, C. O. Shields, I. H. Sudborough, W. Voit: An upper bound for sorting by prefix reversals. In: Theoretical Computer Science. 410, Nr. 36, 2009, S. 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, Nr. 2, 1995, S. 105–120, doi:10.1016/0166-218X(94)00009-3.

[1]

[2]

[3]

[4]