Pancake sort

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken
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 enkel toegelaten is de volgorde van een zekere prefix van de rij om te keren. Een prefix is 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 prefix). Het is de bedoeling om de rij te sorteren van klein naar groot met zo weinig mogelijk omkeringen of flips.

Probleemformulering[bewerken]

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 chefkok 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 n pannenkoeken zijn, wat is dan het maximaal aantal flips (als een functie van n) die 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 p die een permutatie is van de eerste n natuurlijke getallen. Een flip is dan de volgorde omkeren van een prefix (dit zijn de eerste i getallen, met in; dit noemt men een i-flip) van die rij, met als doel de identiteitspermutatie (1 2 ... n) te bekomen met zo weinig mogelijk flips. Noem dit minimumaantal f(p). f(n) is dan het maximum van f(p) voor alle permutaties p; dit is het maximaal aantal flips dat ooit nodig zal zijn om een willekeurige permutatie van n getallen te sorteren. Dit aantal is bekend voor kleine waarden van n maar voor grotere n is f(n) niet exact bekend. De exacte waarde van f(n) voor n=1, 2,... 17 is rij A058986 in OEIS: 0, 1, 3, 4, 5, 7, 8, 9, 10, 11,...

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

Algoritme[bewerken]

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 i)
  • flip de eerste i getallen, zodat het grootste getal vooraan komt
  • flip dan de hele rij, zodat het grootste getal achteraan staat.
  • Herhaal het voorgaande met de rij van de eerste n-1 getallen, en zo verder tot de rij van de eerste twee getallen.

Onder- en bovengrenzen[bewerken]

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 2n-3 flips nodig voor een willekeurige beginrij. Dit is een bovengrens voor 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 f(n) als n ≥ 7:[3]

n + 1 ≤ f(n) ≤ 2n - 6

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

f(n) ≤ (5n+5)/3

wat voor grote n benaderend gelijk is aan 5n/3 of 1,6666... n.[4]

Een nog betere onder- en bovengrens werd gevonden door Hal Sudborough en medewerkers:

15n/14 ≤ f(n) ≤ 18n/11 + O(1)

wat voor grote n ligt tussen 1,0714...n en 1,6363... n.[5]

Het probleem van de aangebrande pannenkoeken[bewerken]

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 g(n), bepaalden zij op:

3n/2 - 1 ≤ g(n) ≤ 2n + 3

Merk op dat het sorteren van de permutatie (n, n-1, ..., 2, 1) in het normale probleem triviaal is (met één flip de ganse 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 g(n) voor n ≥10 terug tot 2n-2. Zij formuleerden het vermoeden dat het moeilijkste geval dat is waarbij initieel alle pannenkoeken gesorteerd zijn naar grootte maar met de aangebrande zijde naar boven, dus in de configuratie (-1, -2,... -n).[6]

Toepassingen[bewerken]

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[bewerken]

De pannenkoekengraaf G3

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

Een pannenkoekengraaf Gn bestaat uit n! knopen en n!(n-1)/2 bogen. Het is een reguliere graaf, waarin elke knoop graad n-1 heeft. Pannenkoekengrafen zijn symmetrisch, hiërarchisch (de graaf Gn is opgebouwd uit n kopieën van Gn-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 f(n).[8] Dit maakt ze aantrekkelijk als schema om parallelle processoren te verbinden.

Moleculaire biologie[bewerken]

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[bewerken]

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 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