Pancake sort

sorteertechniek

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.

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

ProbleemformuleringBewerken

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

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

AlgoritmeBewerken

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  ;
  • flip de eerste   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   getallen, en zo verder tot de rij van de eerste twee getallen.

Onder- en bovengrenzenBewerken

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   flips nodig voor een willekeurige beginrij. Dit is een bovengrens voor   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   als  [3]

 

Bill Gates en prof. Christos Papadimitriou publiceerden in 1979 een efficiënter algoritme en een nieuwe bovengrens voor  

 

wat voor grote   benaderend gelijk is aan  [4]

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

 

Voor grote   zijn deze grenzen ongeveer   en  [5]

Het probleem van de aangebrande pannenkoekenBewerken

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   bepaalden zij op:

 

Interessant is dat het sorteren van de rij in omgekeerde volgorde   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   voor   terug tot   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  [6]

ToepassingenBewerken

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.

NetwerkenBewerken

 
De pannenkoekengraaf G3

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   Elke processor heeft als label een van deze permutaties. De processors kan men beschouwen als knopen in een graaf. Twee processors gelabeld   en   zijn met elkaar verbonden door een ongerichte boog dan en slechts dan, als   uit   kan ontstaan door een flip van een prefix van '  Dergelijk netwerk of graaf noemt men een pancake graph (pannenkoekengraaf). Het is een voorbeeld van een Cayley-graaf.

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

Moleculaire biologieBewerken

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 linkBewerken