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

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 : 0, 1, 3, 4, 5, 7, 8, 9, 10, 11, ...

Het aantal verschillende stapels pannenkoeken die met maximaal  flips kunnen gesorteerd worden, is  (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 ;
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 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  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 

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 

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

Voor grote  zijn deze grenzen ongeveer  en

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

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 

Het pannenkoekenprobleem kan vertaald worden naar een netwerk van parallelle processors, waarin het een effectief routing-algoritme kan vormen tussen de verschillende processors. 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  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.

Externe link 
 Bibliografie van Pancake Sorting

Sorteeralgoritme
Combinatoriek