WikiDer > Pfannkuchen sortieren

Illustration von Pfannkuchen sortieren: Den obersten Stapel von drei Pfannkuchen mit einem Backspatel wenden.

Pfannkuchensortierung (buchstäblich: Pfannkuchen sortieren) ist eine Variation des Sortieren einer Zahlenfolge, die nur die Reihenfolge einer bestimmten Präfix der Reihe umzudrehen. Ein Präfix besteht aus einer Anzahl von Zahlen am Anfang der Zeile; Sie können diese Nummer selbst wählen. Die Methode ist daher auch Sortierung nach Präfixumkehr aufgerufen (Sortieren durch Invertieren eines Präfixes). Ziel ist es, die Reihe mit möglichst wenigen Umkehrungen von der kleinsten zur größten zu sortieren oder Flips.

Problem Formulierung

Ein gewisser Harry Dweighter, verbunden mit dem City College of the City University of New York, formuliert in Amerikanische mathematische Monatszeitschrift ab Dezember 1975^[1] ein Problem, das sich grob wie folgt übersetzen lässt:

Unser Koch ist ziemlich schlampig und wenn er einen Stapel Pfannkuchen backt, sind sie alle unterschiedlich groß. Wenn ich sie also zu einem Kunden bringe, ordne ich sie so um, dass der kleinste ganz oben ist usw. Ich tue dies, indem ich ein Bündel Pfannkuchen oben auf dem Stapel nehme und es umdrehe und dies (mit unterschiedlicher Anzahl von Pfannkuchen) so oft wie nötig wiederhole. Wenn da ${displaystyle n}$ Pfannkuchen sind, was ist die maximale Anzahl Flips (als Funktion von ${displaystyle n}$), dass ich sie jemals einordnen muss?^[2]

Harry Dweighter war ein Pseudonym für den Mathematiker Jacob E. Goodman.

Dieses Problem wurde als Pfannkuchenproblem bekannt (Pfannkuchen-Problem) und die Sortiertechnik wie Pfannkuchen sortieren oder formeller als Sortierung nach Präfixumkehrungen (Sortieren durch invertierende Präfixe).

Beachten Sie, dass die Problemformulierung besagt, dass alle Pfannkuchen unterschiedlich sind. Mathematisch kann der Stack dann ohne Verlust der Allgemeinheit als Reihe dargestellt ${displaystyle p}$ Das hier Permutation ist der erste ${displaystyle n}$ natürliche Zahlen. EIN umdrehen ist dann die Reihenfolge von a . umzukehren Präfix (das sind die ersten ${Anzeigestil i}$ Zahlen, mit ${displaystyle ileq n;}$ das heißt a ${Anzeigestil i}$-flip) dieser Reihe mit dem Ziel, die Reihe mit so wenigen Flips wie möglich vom kleinsten zum größten zu sortieren. Rufen Sie diese Mindestanzahl an ${Anzeigestil f(p).}$ Dann ist ${Anzeigestil f(n)}$ das Maximum von ${Anzeigestil f(p)}$ für alle Permutationen ${displaystyle p}$. Dies ist die maximale Anzahl von Flips, die jemals benötigt werden, um eine zufällige Permutation von zu machen ${displaystyle n}$ Nummern sortieren. Diese Zahl ist bekannt für kleine Werte von ${displaystyle n}$ aber für größere ${displaystyle n}$ ist ${Anzeigestil f(n)}$ nicht genau bekannt. Der genaue Wert von ${Anzeigestil f(n)}$ vor dem ${displaystyle n=1,2,ldots,17}$ ist Reihe A058986 im OEIS: 0, 1, 3, 4, 5, 7, 8, 9, 10, 11, ...

Die Anzahl der verschiedenen Pfannkuchenstapel, die ein Maximum haben ${displaystyle n}$ Flips können sortiert werden, ist Reihe A067607 im OEIS (1, 1, 1, 3, 20, 2, 35, 455, 5804, 73232, ...)

Algorithmus

Ein einfacher Algorithmus zur Lösung dieses Problems ist der folgende:

• finde die größte Zahl in der Reihe und notiere ihre Position, nenne sie ${Anzeigestil i}$;
• dreh den ersten ${Anzeigestil i}$ Zahlen, so dass die größte Zahl zuerst kommt
• Drehen Sie dann die gesamte Reihe um und lassen Sie die größte Zahl am Ende.
• Wiederholen Sie das obige mit der Reihe des ersten ${Anzeigestil n-1}$ Zahlen usw. bis zur Reihe der ersten beiden Zahlen.

Untere und obere Grenze

Der obige Algorithmus erfordert höchstens zwei Flips pro Iteration mit Ausnahme des letzten; bleiben nur noch zwei Zahlen übrig, ist höchstens ein Flip erforderlich. So gibt es höchstens ${Anzeigestil 2n-3}$ Flips für jede Startreihe erforderlich. Dies ist eine Obergrenze für ${Anzeigestil f(n)}$ was jedoch verfeinert werden kann. 1977 wurden Michael R. Garey, David S. Johnson und Shen Lin of Bell Labs folgende Unter- und Obergrenzen für ${Anzeigestil f(n)}$ wenn ${displaystyle ngeq 7:}$^[3]

${displaystyle n 1leq f(n)leq 2n-6}$

Bill Gates und Prof. Christos Papadimitriou veröffentlichten 1979 einen effizienteren Algorithmus und eine neue Obergrenze für ${Anzeigestil f(n):}$

${displaystyle f(n)leq { frac {1}{3}}(5n 5)}$

was für große ${displaystyle n}$ ist ungefähr gleich ${Displaystil 5n/3ca. 1{,}67n.}$^[4]

Noch bessere Unter- und Obergrenzen wurden von Hal Sudborough und Mitarbeitern gefunden:

${displaystyle { frac {15}{14}}nleq f(n)leq { frac {18}{11}}n O(1)}$

für große ${displaystyle n}$ sind diese Grenzen ungefähr? ${Displaystil 1{,}0714n}$ und ${Displaystil 1{,}6363n.}$^[5]

Das Problem der verbrannten Pfannkuchen

Eine schwierigere Variante des Pfannkuchenproblems ist es Problem mit verbrannten Pfannkuchen, in dem eine Seite jedes Pfannkuchens verbrannt wird. Nach dem Sortieren sollten alle Pfannkuchen mit der Seite nach unten gebrannt werden.

Dieses Problem wird auch mit bezeichnet Vorzeichenumkehrung mit Vorzeichen. Dies kann man zwar darstellen, indem man jeder Zahl ein Vorzeichen gibt; negativ bedeutet dann verbrannte Seite nach oben. Ein Flip ändert das Vorzeichen aller beteiligten Zahlen. Das Ziel ist es, die Zahlen zu sortieren und keine negativen Zahlen zu hinterlassen. Bei diesem Problem ist ein 1-Flip (nur den oberen Pfannkuchen umdrehen) möglich; im normalen Problem ist das eine nutzlose Operation.

Diese Variante wurde von Bill Gates und Papadimitriou in ihrer Arbeit von 1979 eingeführt Unter- und Obergrenzen für die maximale Anzahl von Flips, jetzt bezeichnet mit ${Anzeigestil g(n)}$ sie stellten fest:

${displaystyle { frac {3}{2}}n-1leq g(n)leq 2n 3}$

Interessanterweise wird die Zeile umgekehrt sortiert ${Anzeigestil (n,n-1,ldots,2,1)}$ im gewöhnlichen Problem ist trivial (die ganze Reihe mit einem Flip umzukehren), aber im verbrannt Ausführung schwierig. Das Sortieren (2 1) erfordert jetzt nicht 1 sondern 3 Flips: einen 1-Flip (-2 1), einen 2-Flip (-1 2) und einen 1-Flip (1 2).

Dieses Thema wurde auch von David S. Cohen untersucht, der später als David X. Cohen einer der Produzenten der Zeichentrickserie wurde. futurama wurde. Er und Manuel Blum brachte die Obergrenze von ${Anzeigestil g(n)}$ vor dem ${displaystyle ngeq 10}$ zurück zu ${Anzeigestil 2n-2.}$ Sie formulierten die Hypothese, dass der schwierigste Fall darin besteht, dass zunächst alle Pfannkuchen nach Größe sortiert werden, jedoch mit der verbrannten Seite nach oben, also in der Konfiguration ${Anzeigestil (-1,-2,ldots,-n).}$^[6]

Anwendungen

Obwohl das Pancake-Sorting-Problem in erster Linie ein mathematisches Problem im Bereich der Freizeitmathematik ist, scheint es einige (potenzielle) Anwendungen zu haben.

Vernetzung

Der Pfannkuchenzähler G₃

Das Pfannkuchenproblem kann in ein übersetzt werden Netzwerk von Parallelprozessoren, in denen es einen effektiven Routing-Algorithmus zwischen den verschiedenen Prozessoren bilden kann.^[7] Ein solches Netzwerk hat so viele Prozessoren, wie es Permutationen von ${Anzeigestil (1.2ldots, n).}$ Jeder Prozessor ist mit einer dieser Permutationen gekennzeichnet. Die Prozessoren kann man sich als Knoten in a . vorstellen Anzahl. Zwei Prozessoren beschriftet ${Anzeigestil u}$ und ${Anzeigestil v}$ sind genau dann durch einen ungerichteten Bogen verbunden, wenn ${Anzeigestil v}$ von ${Anzeigestil v}$ kann durch eine Umkehrung eines Präfixes von ' verursacht werden${Anzeigestil u.}$ Ein solches Netzwerk oder ein solcher Graph heißt a Pfannkuchen-Grafik (Pfannkuchen zählen). Es ist ein Beispiel für a Cayley Earl.

Eine Pfannkuchenzählung ${displaystyle G_{n}}$ besteht aus ${displaystyle n!}$ Knöpfe und ${Anzeigestil n!(n-1)/2}$ Bögen. Es ist ein regulärer Graph, in dem jeder Knoten den Grad . hat ${Anzeigestil n-1}$ hast. Pfannkuchengraphen sind symmetrisch, hierarchisch (der Graph ${displaystyle G_{n}}$ wird gemacht aus ${displaystyle n}$ Kopien von ${Displaystil G_{n-1}}$), maximal fehlertolerant und haben einen minimalen Durchmesser (dies ist die maximale Länge des kürzesten Weges zwischen zwei Knoten im Graphen), nämlich ${displaystyle f_{n}.}$^[8] Dies macht sie als Schema zum Verbinden paralleler Prozessoren attraktiv.

Molekularbiologie

Sortierung nach Präfix-Umkehrungen Es stellt sich heraus, dass es ein Gegenstück in der Genetik. Änderungen in genommen die zur Evolution neuer Arten führen, erfolgen oft durch Übergänge, die die Reihenfolge einer Reihe von aufeinanderfolgenden Gene umkehren. Dies kann modelliert werden mit signierte Präfixumkehrung. Die Suche nach der schnellsten Evolution oder der kleinstmöglichen Anzahl von Übergängen führt zur Lösung dieses Problems.^[9]

Externer Link

• Bibliographie von Pfannkuchensortierung