Pancake sort

Illustratie van pancake sorting: met een bakspatel wordt de bovenste stapel van drie pannenkoeken omgekeerd.

Pancake sorting (letterlijk: pannenkoekensorteren) is een variatie op het sorteren van een rij getallen, waarbij het alleen toegestaan is de volgorde van een zeker prefix van de rij om te keren. Een prefix bestaat uit een aantal getallen aan het begin van de rij; dat aantal mag men zelf kiezen. De methode wordt daarom ook sorting by prefix reversal genoemd (sorteren door omkeren van een prefix). Het is de bedoeling om de rij te sorteren van klein naar groot met zo weinig mogelijk omkeringen of flips.

Probleemformulering

Een zekere Harry Dweighter, verbonden aan The City College of the City University of New York, formuleerde in American Mathematical Monthly van december 1975^[1] een probleem dat vrij vertaald als volgt luidt:

Onze chef-kok is nogal slordig en als hij een stapel pannenkoeken bakt hebben ze allemaal een andere grootte. Dus, als ik ze naar een klant breng, herschik ik ze zo dat de kleinste bovenaan komt, en zo verder, tot de grootste onderaan. Ik doe dat door een bundel pannenkoeken bovenaan de stapel te nemen en die om te draaien, en dit herhaal ik (met verschillende aantallen pannenkoeken) zo vaak als nodig. Als er ${\displaystyle n}$ pannenkoeken zijn, wat is dan het maximaal aantal flips (als een functie van ${\displaystyle n}$) dat ik ooit zal nodig hebben om ze te rangschikken?^[2]

Harry Dweighter was overigens een pseudoniem voor de wiskundige Jacob E. Goodman.

Dit probleem raakte bekend als het pannenkoekenprobleem (pancake problem) en de sorteertechniek als pancake sorting of formeler als sorting by prefix reversals (sorteren door omkeren van prefixen).

Merk op dat in de probleemformulering gesteld wordt dat alle pannenkoeken verschillend zijn. In wiskundige termen kan de stapel dan zonder verlies van algemeenheid voorgesteld worden als een rij ${\displaystyle p}$ die een permutatie is van de eerste ${\displaystyle n}$ natuurlijke getallen. Een flip is dan de volgorde omkeren van een prefix (dit zijn de eerste ${\displaystyle i}$ getallen, met ${\displaystyle i\leq n;}$ dit noemt men een ${\displaystyle i}$-flip) van die rij, met als doel de rij van klein naar groot te sorteren met zo weinig mogelijk flips. Noem dit minimumaantal ${\displaystyle f(p).}$ Dan is ${\displaystyle f(n)}$ het maximum van ${\displaystyle f(p)}$ voor alle permutaties ${\displaystyle p}$. Dit is het maximaal aantal flips dat ooit nodig zal zijn om een willekeurige permutatie van ${\displaystyle n}$ getallen te sorteren. Dit aantal is bekend voor kleine waarden van ${\displaystyle n}$ maar voor grotere ${\displaystyle n}$ is ${\displaystyle f(n)}$ niet exact bekend. De exacte waarde van ${\displaystyle f(n)}$ voor ${\displaystyle n=1,2,\ldots ,17}$ is rij A058986 in OEIS: 0, 1, 3, 4, 5, 7, 8, 9, 10, 11, ...

Het aantal verschillende stapels pannenkoeken die met maximaal ${\displaystyle n}$ flips kunnen gesorteerd worden, is rij A067607 in OEIS (1, 1, 1, 3, 20, 2, 35, 455, 5804, 73232, ...)

Algoritme

Een eenvoudig algoritme om dit probleem op te lossen is het volgende:

• zoek het grootste getal in de rij en noteer de positie daarvan, noem dit ${\displaystyle i}$;
• flip de eerste ${\displaystyle i}$ getallen, zodat het grootste getal vooraan komt
• flip dan de hele rij, waardoor het grootste getal achteraan staat.
• Herhaal het voorgaande met de rij van de eerste ${\displaystyle n-1}$ getallen, en zo verder tot de rij van de eerste twee getallen.

Onder- en bovengrenzen

Bovenstaand algoritme vereist hoogstens twee flips per iteratie behalve voor de laatste; als er slechts twee getallen overblijven, is hoogstens één flip nodig. Op die manier zijn er dus hoogstens ${\displaystyle 2n-3}$ flips nodig voor een willekeurige beginrij. Dit is een bovengrens voor ${\displaystyle f(n)}$ die echter verfijnd kan worden. In 1977 gaven Michael R. Garey, David S. Johnson en Shen Lin van Bell Labs de volgende onder- en bovengrens aan voor ${\displaystyle f(n)}$ als ${\displaystyle n\geq 7:}$^[3]

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

Bill Gates en prof. Christos Papadimitriou publiceerden in 1979 een efficiënter algoritme en een nieuwe bovengrens voor ${\displaystyle f(n):}$

${\displaystyle f(n)\leq {\tfrac {1}{3}}(5n+5)}$

wat voor grote ${\displaystyle n}$ benaderend gelijk is aan ${\displaystyle 5n/3\approx 1{,}67n.}$^[4]

Nog betere onder- en bovengrenzen werden gevonden door Hal Sudborough en medewerkers:

${\displaystyle {\tfrac {15}{14}}n\leq f(n)\leq {\tfrac {18}{11}}n+O(1)}$

Voor grote ${\displaystyle n}$ zijn deze grenzen ongeveer ${\displaystyle 1{,}0714n}$ en ${\displaystyle 1{,}6363n.}$^[5]

Het probleem van de aangebrande pannenkoeken

Een moeilijkere variatie op het pannenkoekenprobleem is het burnt pancake problem, waarin een zijde van elke pannenkoek aangebrand is. Na sortering moeten alle pannenkoeken met de aangebrande zijde naar beneden liggen.

Dit probleem wordt ook aangeduid met signed prefix reversal. Men kan dit inderdaad voorstellen door aan elk getal een teken te geven; negatief betekent dan aangebrande kant naar boven. Bij een flip verandert het teken van alle betrokken getallen. Het doel is om de getallen gesorteerd te krijgen en geen negatieve getallen over te houden. In dit probleem is een 1-flip (alleen de bovenste pannenkoek omdraaien) mogelijk; in het normale probleem is dat een nutteloze operatie.

Deze variante werd geïntroduceerd door Bill Gates en Papadimitriou in hun paper uit 1979. Onder- en bovengrenzen voor het maximaal aantal flips, nu aangeduid met ${\displaystyle g(n)}$ bepaalden zij op:

${\displaystyle {\tfrac {3}{2}}n-1\leq g(n)\leq 2n+3}$

Interessant is dat het sorteren van de rij in omgekeerde volgorde ${\displaystyle (n,n-1,\ldots ,2,1)}$ in het gewone probleem triviaal is (met één flip de hele rij omkeren), maar in de aangebrande versie juist moeilijk. Om (2 1) te sorteren zijn nu niet 1 maar 3 flips nodig: een 1-flip (-2 1), een 2-flip (-1 2) en een 1-flip (1 2).

Dit probleem werd ook onderzocht door David S. Cohen, die later als David X. Cohen een van de producenten van de animatieserie Futurama werd. Hij en Manuel Blum brachten de bovengrens van ${\displaystyle g(n)}$ voor ${\displaystyle n\geq 10}$ terug tot ${\displaystyle 2n-2.}$ Zij formuleerden het vermoeden dat het moeilijkste geval dat is waarbij aanvankelijk alle pannenkoeken gesorteerd zijn naar grootte maar met de aangebrande zijde naar boven, dus in de configuratie ${\displaystyle (-1,-2,\ldots ,-n).}$^[6]

Toepassingen

Hoewel het pannenkoekensorteerprobleem in de eerste plaats een wiskundig probleem in de sfeer van de recreatieve wiskunde is, blijkt het toch een paar (potentiële) toepassingen te hebben.

Netwerken

De pannenkoekengraaf G₃

Het pannenkoekenprobleem kan vertaald worden naar een netwerk van parallelle processors, waarin het een effectief routing-algoritme kan vormen tussen de verschillende processors.^[7] Zo'n netwerk heeft evenveel processors als er permutaties zijn van ${\displaystyle (1,2\ldots ,n).}$ Elke processor heeft als label een van deze permutaties. De processors kan men beschouwen als knopen in een graaf. Twee processors gelabeld ${\displaystyle u}$ en ${\displaystyle v}$ zijn met elkaar verbonden door een ongerichte boog dan en slechts dan, als ${\displaystyle v}$ uit ${\displaystyle v}$ kan ontstaan door een flip van een prefix van '${\displaystyle u.}$ Dergelijk netwerk of graaf noemt men een pancake graph (pannenkoekengraaf). Het is een voorbeeld van een Cayley-graaf.

Een pannenkoekengraaf ${\displaystyle G_{n}}$ bestaat uit ${\displaystyle n!}$ knopen en ${\displaystyle n!(n-1)/2}$ bogen. Het is een reguliere graaf, waarin elke knoop graad ${\displaystyle n-1}$ heeft. Pannenkoekengrafen zijn symmetrisch, hiërarchisch (de graaf ${\displaystyle G_{n}}$ is opgebouwd uit ${\displaystyle n}$ kopieën van ${\displaystyle G_{n-1}}$), maximaal fout-tolerant, en hebben een minimale diameter (dit is de maximale lengte van het kortste pad tussen twee knopen in de graaf), namelijk ${\displaystyle f_{n}.}$^[8] Dit maakt ze aantrekkelijk als schema om parallelle processoren te verbinden.

Moleculaire biologie

Sorting by prefix reversals blijkt een tegenhanger te hebben in de genetica. Veranderingen in genomen die leiden tot de evolutie van nieuwe soorten gebeuren dikwijls door transities die de volgorde van een aantal opeenvolgende genen omkeren. Dit kan men modelleren met behulp van signed prefix reversal. Het zoeken naar de snelste evolutie of het kleinst mogelijke aantal transities komt dan neer op het oplossen van dat probleem.^[9]

Externe link

• Bibliografie van Pancake Sorting

Bronnen, noten en/of referenties

1. Problem E2569 in American Mathematical Monthly, vol. 82 nr. 10 (December 1975), blz. 1010
2. De originele tekst luidt: The chef in our place is sloppy, and when he prepares a stack of pancakes they come out all different sizes. Therefore, when I deliver them to a customer, on the way to the table I rearrange them (so that the smallest winds up on top, and so on, down to the largest on the bottom) by grabbing several from the top and flipping them over, repeating this (varying the number I flip) as many times as necessary. If there are n pancakes, what is the maximum number of flips (as a function of n) that I will ever have to use to rearrange them?
3. Am. Math. Monthly, vol. 84 nr. 4 (April 1977), blz. 296
4. William H. Gates, Christos H. Papadimitriou. (1979) - Bounds for sorting by prefix reversal, Discrete Mathematics, vol. 27, pp. 47-57
5. B. Chitturi, W. Fahle, Z. Meng, L. Morales, C.O. Shields, I.H. Sudborough, W. Voit "An (18/11)n upper bound for sorting by prefix reversals." Theoretical Computer Science, Vol. 410 nr. 36 (31 augustus 2009), blz. 3372-3390. DOI:10.1016/j.tcs.2008.04.045
6. David S. Cohen, Manuel Blum. "On the problem of sorting burnt pancakes." Discrete Applied Mathematics, vol. 61 nr. 2 (28 juli 1995), blz. 105-120. DOI:10.1016/0166-218X(94)00009-3
7. M. H. Heydari, I.H. Sudborough. "On the Diameter of the Pancake Network", Journal of Algorithms, vol. 25 nr. 1 (oktober 1997), blz. 67-94. DOI:10.1006/jagm.1997.0874
8. M.F. Zerarka, S. Femmam, R. Aschheim. "Embedding ${\displaystyle n}$-Dimensional Crossed Hypercube into Pancake Graphs." British Journal of Mathematics & Computer Science, vol. 2 nr. 1 (2012) blz. 1-20.
9. S. Hannenhalli, P. A. Pevzner. "Transforming cabbage into turnip: polynomial algorithm for sorting signed permutations by reversals." Journal of the ACM, vol. 46 nr. 1 (1999), blz. 1-27. DOI:10.1145/300515.300516