Palacsintarendezés forrásának megtekintése

[[File:Pancake sort operation.png|right|frame|A palacsintarendezés fő művelete. A spatulával  megfordítják a felső három palacsintát, az eredmény lent látható. Az égetett palacsinta-problémában a művelet után az átfordított palacsinták tetején lenne az égés, nem az aljukon.]]
A '''palacsintarendezés''' ''(pancake sorting)'' az a matematikai probléma, melynek során különböző méretű [[Palacsinta|palacsintákból]] álló oszlopot nagyság szerinti sorba rendeznek oly módon, hogy az oszlopba bárhol beszúrható egy fordítólapát, és az összes fölötte lévő palacsinta megfordítható vele. A '''palacsintaszám''' ''(pancake number)'' az adott számú palacsinta rendezéséhez szükséges minimális fordítások száma. A problémát ebben a formában először [[Jacob E. Goodman]] amerikai mértanász vetette fel.<ref>{{cite news|author=[[Simon Singh]]| title=Flipping pancakes with mathematics|newspaper=[[The Guardian]]| date=November 14, 2013| url=https://www.theguardian.com/science/blog/2013/nov/14/flipping-pancakes-mathematics-jacob-goodman| accessdate=March 25, 2014}}</ref> A [[Rendezés (programozás)|rendezési probléma]] egy változata, melyben az egyetlen lehetséges művelet a sorozat valamely prefixumának (a karakterlánc elejétől kezdődő rész-sztringnek) megfordítása. A hagyományos rendezési algoritmusokkal ellentétben, melyeknél általában az összehasonlítások számának minimalizálására törekszenek, itt a cél a lehető legkevesebb megfordítást elvégezni. A probléma egy változata „égetett” palacsintákkal foglalkozik, melyek oldalait megkülönböztetjük (az egyik égett), és a palacsintákat nem egyszerűen nagyság szerinti sorba kell rendezni, hanem a rendezés végén az égett oldalukkal lefelé kell lenniük.

==A palacsintaproblémák==

===Az eredeti palacsintaprobléma===
[[File:Tri de 6 crêpes.gif|thumb|Hat palacsintából álló oszlop. Az {5 ;&nbsp;3 ;&nbsp;6 ;&nbsp;1 ;&nbsp;4 ;&nbsp;2} kiindulási állapot látható, a két hat elemű konfiguráció egyike, ami 7 manipulációt igényel (a másik a {4 ;&nbsp;6 ;&nbsp;2 ;&nbsp;5 ;&nbsp;1 ;&nbsp;3}).]]
{| class="wikitable"
|+ Palacsintaszámok<br />{{OEIS|A058986}}
|<math>n</math>
| 1 || 2 || 3 || 4 || 5 || 6 || 7 || 8 || style="text-align:right"| 9 || 10 || 11 || 12 || 13 || 14 || 15 || 16 || 17
|-
|<math>P_n</math>
| 0 || 1 || 3 || 4 || 5 || 7 || 8 || 9 || 10 || 11 || 13 || 14 || 15 || 16 || 17 || 18 || 19
|}

Az {{math|''n''}} palacsintát tartalmazó oszlop rendezéséhez mindig elégséges, minimális átfordítások száma <math>\frac{15}{14}n</math> és <math>\frac{18}{11}n</math> (kb. <math>1,07n</math> és <math>1,64n</math>) között van, de a pontos érték nem ismert.<ref>{{Cite book|author=Fertin, G. and Labarre, A. and Rusu, I. and Tannier, E. and Vialette, S. |title=Combinatorics of Genome Rearrangements|publisher= The MIT Press|year= 2009|isbn=9780262062824}}</ref>

A legegyszerűbb palacsintarendező algoritmusnak <math>2n-3</math> lépésre van szüksége. Ez a [[kiválasztásos rendezés]] olyan változata, melyben a nem a helyén lévő palacsinták közül a legnagyobbat egy átfordítással a tetejére, majd egy másik átfordítással közvetlenül a helyére juttatjuk el, addig ismételve a folyamatot, míg az összes palacsinta a helyére nem kerül.

1979-ben [[Bill Gates]] és [[Christos Papadimitriou]]<ref name=Gates1979/> <math>\frac{5}{3}n</math> felső korlátot igazolt. Ezt 30 évvel később <math>\frac{18}{11}n</math>-re javította a [[University of Texas at Dallas]] egyetem  [[Hal Sudborough]] által vezetett kutatócsoportja.<ref name="Sudborough">{{cite web|title=Team Bests Young Bill Gates With Improved Answer to So-Called Pancake Problem in Mathematics|publisher=University of Texas at Dallas News Center|date=September 17, 2008|url=http://www.utdallas.edu/news/2008/09/17-002.php?WT.mc_id=NewsEmails&WT.mc_ev=EmailOpen|accessdate=November 10, 2008|quote=A team of UT Dallas computer science students and their faculty adviser have improved upon a longstanding solution to a mathematical conundrum known as the pancake problem. The previous best solution, which stood for almost 30 years, was devised by Bill Gates and one of his Harvard instructors, Christos Papadimitriou, several years before Microsoft was established.|archiveurl=https://www.webcitation.org/66htPePZH?url=http://www.utdallas.edu/news/2008/09/17-002.php?WT.mc_id=NewsEmails|archivedate=2012-04-05}}</ref> (Chitturi et al., 2009<ref>{{Cite journal|last=Chitturi|first=B.|last2=Fahle|first2=W.|last3=Meng|first3=Z.|last4=Morales|first4=L.|last5=Shields|first5=C. O.|last6=Sudborough|first6=I. H.|last7=Voit|first7=W.|date=2009-08-31|title=An (18/11)n upper bound for sorting by prefix reversals|url=http://www.sciencedirect.com/science/article/pii/S0304397508003575|journal=Theoretical Computer Science|series=Graphs, Games and Computation: Dedicated to Professor Burkhard Monien on the Occasion of his 65th Birthday|volume=410|issue=36|pages=3372–3390|doi=10.1016/j.tcs.2008.04.045}}</ref>).

2011-ben Laurent Bulteau, Guillaume Fertin és Irena Rusu<ref>{{Cite journal|journal=Journal of Computer and System Sciences|doi=10.1016/j.jcss.2015.02.003|title=Pancake Flipping Is Hard|last1=Bulteau|first1=Laurent|last2=Fertin|first2=Guillaume|last3=Rusu|first3=Irena|volume=81|number=8|pages=1556–1574|arxiv=1111.0434v1}}</ref> bebizonyították, hogy egy adott palacsintaoszlop rendezéséhez szükséges legrövidebb átfordítás-sorozat megtalálása [[NP-nehéz]] feladat.

===Az égetett palacsinta problémája===
Az '''égetett palacsinta-problémaként''' ''(burnt pancake problem)'' ismert változatban a palacsinták alja megégett, és a rendezés végén minden palacsintának az égett oldalával alul kell elhelyezkednie. Ebben az ''előjeles permutációban'' ha az ''i'' palacsinta égett oldalával felfelé van, akkor a permutációban az ''i'' helyén az ''i`'' negatív elem szerepel. Erre a változatra David S. Cohen ([[David X. Cohen]]) és [[Manuel Blum]] 1995-ben a következő állítást igazolták: <math>3n/2\leq P'_n\leq 2n-2</math> (ahol a felső korlát csak <math>n>9</math>-től válik igazzá).<ref>David S. Cohen, Manuel Blum: ''On the problem of sorting burnt pancakes.'' In: ''Discrete Applied Mathematics.'' 61, Nr. 2, 1995, S. 105–120. [[DOI:10.1016/0166-218X(94)00009-3]].</ref>

2008-ban egyetemi hallgatók olyan [[DNS-alapú számítástechnika|bakteriális számítógépet]] építettek, ami képes volt az égetett palacsinta-probléma egyszerű változatának megoldására úgy, hogy az ''[[Escherichia coli|E. coli]]'' bacilusok DNS-szakaszokat fordítottak meg az égetett palacsinták analógiájára. A DNS-molekula rendelkezik irányítással (5' és 3') és sorrenddel ([[promoter]]ek a kódoló szakaszok előtt). Bár a DNS-átfordítások által képviselt számítási teljesítmény alacsony volt, egy tenyészetben a baktériumok nagy száma erősen párhuzamosítható feladatok megoldására alkalmassá teheti őket. A kísérleti elrendezésben a baktériumok akkor oldották meg a problémát, amikor antibiotikum-ellenállóvá váltak.<ref>{{Cite journal|doi=10.1186/1754-1611-2-8|title=Engineering bacteria to solve the Burnt Pancake Problem|year=2008|last1=Haynes|first1=Karmella A|last2=Broderick|first2=Marian L|last3=Brown|first3=Adam D|last4=Butner|first4=Trevor L|last5=Dickson|first5=James O|last6=Harden|first6=W Lance|last7=Heard|first7=Lane H|last8=Jessen|first8=Eric L|last9=Malloy|first9=Kelly J|journal=Journal of Biological Engineering|volume=2|pages=8|pmid=18492232|pmc=2427008|last10=Ogden|first10=Brad J|last11=Rosemond|first11=Sabriya|last12=Simpson|first12=Samantha|last13=Zwack|first13=Erin|last14=Campbell|first14=A Malcolm|last15=Eckdahl|first15=Todd T|last16=Heyer|first16=Laurie J|last17=Poet|first17=Jeffrey L}}</ref>
{| class="wikitable"
|+ Égetett palacsinta-számok<br />{{OEIS|A078941}}
|<math>n</math>
| 1 || 2 || 3 || 4 || style="text-align:right" | 5 || style="text-align:right" | 6 || style="text-align:right" | 7 || style="text-align:right" | 8 || style="text-align:right" | 9 || 10 || 11 || 12
|-
|<math>P'_n</math>
| 1 || 4 || 6 || 8 || 10 || 12 || 14 || 15 || 17 || 18 || 19 || 21
|}

===Az egyforma palacsinták problémája===
A feladatot az indiai kenyér ([[csapáti]] vagy [[róti]]) elkészítési módja ihlette. A kiindulási állapotban az összes róti egy oszlopba van felhalmozva, majd a szakács lapáttal átfordítja őket, hogy minden róti minden oldala egy ideig a tűz közvetlen közelében sülhessen. Különböző változatok képzelhetők el: a rótikat tekinthetjük egy- vagy kétoldalasnak, megtilthatjuk, hogy ugyanahhoz a rótihoz kétszer hozzáérjünk. A probléma ezen változatát Arka Roychowdhury vizsgálta elsőként.<ref>https://arkaroychowdhury1.wordpress.com/portfolio/flippingpancakes/</ref>

===A palacsintaprobléma karakterláncokon===
A fenti problémákban a palacsinták egyediek voltak, tehát az elvégzett prefix-megfordítási művelet ''[[permutáció]]''. Karakterláncok esetében azonban a szimbólumok ismétlődhetnek, ami csökkentheti az elvégzendő prefix-megfordítási műveletek számát. Chitturi and Sudborough (2010), illetve Hurkens et al. (2007) egymástól függetlenül megmutatták, hogy két kompatibilis karakterlánc között minimális számú prefix-megfordítási művelettel történő transzformáció [[NP-nehéz]] feladat. Néhány korlátot is meghatároztak erre. Hurkens et al. pontos algoritmust adott bináris és ternáris karakterláncok rendezésére. Chitturi<ref name=":0">{{cite journal|title=A NOTE ON COMPLEXITY OF GENETIC MUTATIONS|journal=Discrete Mathematics, Algorithms and Applications|volume= 03| issue = 03|doi=10.1142/S1793830911001206}}</ref>  (2011) bizonyította azt is, hogy a két kompatibilis, előjeles karakterlánc között minimális számú prefix-megfordítási művelettel történő transzformáció – ami az égetett palacsinta-probléma karakterlánc-változata – szintén [[NP-nehéz]] feladat.

==Története==
Bár sokszor csak oktatási eszköznek tekintik, a palacsintarendezésnek fontos alkalmazásai vannak párhuzamos processzorhálózatok területén a processzorok között hatékony útválasztási algoritmus biztosításában.<ref>{{Cite journal| last1 = Gargano | first1 = L.
 | last2 = Vaccaro | first2 = U.
 | last3 = Vozella | first3 = A.
 | doi = 10.1016/0020-0190(93)90043-9
 | issue = 6
 | journal = Information Processing Letters
 | mr = 1216942
 | pages = 315–320
 | title = Fault tolerant routing in the star and pancake interconnection networks
 | volume = 45
 | year = 1993}}.</ref><ref>{{Cite book| last1 = Kaneko | first1 = K.
 | last2 = Peng | first2 = S.
 | contribution = Disjoint paths routing in pancake graphs
 | doi = 10.1109/PDCAT.2006.56
 | pages = 254–259
 | title = Proceedings of Seventh International Conference on Parallel and Distributed Computing, Applications and Technologies, 2006 (PDCAT '06)
 | year = 2006| isbn = 0-7695-2736-1}}.</ref>

A probléma népszerűségét az is növelte, hogy ebben a témában jelent meg az egyedüli matematikai publikációja a [[Microsoft]] alapítójának, [[Bill Gates]]nek (mint William Gates), ''Bounds for Sorting by Prefix Reversal'' címmel. Az 1979-ben megjelent publikációban leír egy hatékony palacsintarendező algoritmust.<ref name=Gates1979>{{cite journal |url=http://www.cs.berkeley.edu/~christos/papers/Bounds%20For%20Sorting%20By%20Prefix%20Reversal.pdf |title=Bounds for Sorting by Prefix Reversal |journal=[[Discrete Mathematics]] |volume=27 |pages=47–57 |year=1979 |doi=10.1016/0012-365X(79)90068-2 |last=Gates |first=W. |last2=Papadimitriou |first2=C. |authorlink1=Bill Gates |authorlink2=Christos Papadimitriou |accessdate=2017-07-30 |archiveurl=https://web.archive.org/web/20070610154429/http://www.cs.berkeley.edu/~christos/papers/Bounds%20For%20Sorting%20By%20Prefix%20Reversal.pdf |archivedate=2007-06-10 }}</ref> Ráadásul a ''[[Futurama]]'' társszerzője, [[David X. Cohen]] (mint David S. Cohen) is foglalkozott az égetett palacsinta-problémával.<ref>{{Cite journal|author1=Cohen D.S. |author2= Blum, M.|doi=10.1016/0166-218X(94)00009-3|title=On the problem of sorting burnt pancakes|year=1995|journal=Discrete Applied Mathematics|volume=61|issue=2|pages=105|authorlink1=David X. Cohen|authorlink2=Manuel Blum}}</ref>

Néhány kapcsolódó problémát is tanulmányoztak a közelmúltban, az előjeles, megfordítással történő rendezés és a megfordítással történő rendezés problémáit. Ezeknél nem csak a sztring elejétől kezdődő, prefix-megfordítást lehet végezni, hanem bármilyen karakterlánc megfordítható. Bár az előjeles esetre hatékony egzakt algoritmust sikerült találni,<ref>Kaplan, H., Shamir, R. and [[Robert Tarjan|Tarjan, R.E.]] "Faster and Simpler Algorithm for Sorting Signed Permutations by Reversals." ''Proc.'' 8th ''ACM-SIAM SODA'' (1997), 178-187, 1997.</ref> az előjel nélkülinek még bizonyos konstans faktorral történő közelítése is nehéznek bizonyult,<ref>Berman, P. and [[Marek Karpinski|Karpinski, M.]] [http://theory.cs.uni-bonn.de/ftp/reports/cs-reports/1998/85193-CS.ps.gz "On Some Tighter Inapproximability Results."] ''Proc.'' 26th ''ICALP'' (1999), ''LNCS'' 1644, ''Springer'', 200-209, 1999.</ref> bár polinom időben közelíthetőnek bizonyult 1,375-ös approximációs faktorral.<ref>Berman, P., [[Marek Karpinski|Karpinski M.]] and Hannenhalli, S., [http://theory.cs.uni-bonn.de/ftp/reports/cs-reports/2001/85228-CS.ps.gz "1.375-Approximation Algorithms for Sorting by Reversals."] ''Proc.'' 10th ''ESA'' (2002), ''LNCS'' 2461, ''Springer'', 200-210, 2002.</ref>

==Palacsintagráfok==
{{fő|Palacsintagráf}}
[[File:Pancake graph g3.svg|thumb|A P<sub>3</sub> palacsintagráf]]
[[File:Pancake graph g4.svg|thumb|A P<sub>4</sub> palacsintagráf rekurzívan előállítható a P<sub>3</sub> 4 kópiájából úgy, hogy az {1, 2, 3, 4} halmaz más-más elemét fűzzük hozzá az egyes kópiákhoz.]]

Egy '''''n''-palacsintagráf''', jelölése P<sub>n</sub> olyan egyszerű, irányítatlan, hurokmentes [[gráf]], melynek csúcshalmaza az 1,2,...,n számok permutációinak (sorbaállításainak) halmaza. Két permutáció között akkor húzódik él, ha az egyik tranzitív módon átvihető a másikba egy kezdőszeletének megfordításával ''(prefix reversal)''. A palacsintarendezési probléma és a palacsintagráf [[átmérő (gráfelmélet)|átmérőjének]] meghatározása egymással ekvivalens.<ref name="pancake17">{{Cite journal|last=Asai|first=Shogo|last2=Kounoike|first2=Yuusuke||last3=Shinano|first3=Yuji|last4=Kaneko|first4=Keiichi|date=2006-09-01|title=Computing the Diameter of 17-Pancake Graph Using a PC Cluster.|url=https://link.springer.com/chapter/10.1007/11823285_117 |journal=Euro-Par 2006 Parallel Processing: 12th International Euro-Par Conference|doi=10.1007/11823285_117}}</ref>

Az ''n'' méretű palacsintagráf, P<sub>n</sub> rekurzívan előállítható a P<sub>n&minus;1</sub> palacsintagráf ''n'' kópiájából oly módon, hogy az {1, 2, …, n} halmaz más-más elemét fűzzük hozzá az egyes kópiákhoz.

A P<sub>n</sub> palacsintagráf [[reguláris gráf|reguláris]], csúcsainak száma ''n!'', [[fokszám (gráfelmélet)|fokszáma]] ''n&minus;1''. [[Girthparaméter]]e:

<math>g(P_n) = 6 \text{, ha } n>2</math>.

A P<sub>n</sub> palacsintagráf &gamma;(P<sub>n</sub>) [[gráf beágyazása|génuszáról]] elmondható, hogy:<ref name="ongenus">{{Cite journal|last=Nguyen|first=Quan|last2=Bettayeb|first2=Said|date=2009-11-05|title=On the Genus of Pancake Network.|url=http://ccis2k.org/iajit/PDF/vol.8,no.3/1247.pdf|journal=The International Arab Journal of Information Technology|volume=8|issue=3|pages=289–292|accessdate=2017-07-30|archiveurl=https://web.archive.org/web/20170809203553/http://ccis2k.org/iajit/PDF/vol.8,no.3/1247.pdf|archivedate=2017-08-09}}</ref>

<math>n!\left( \frac{n-4}{6} \right)+1 \le \gamma(P_n) \le n!\left( \frac{n-3}{4} \right)-\frac{n}{2}+1 </math>

A palacsintagráfok számos érdekes tulajdonsággal rendelkeznek – szimmetrikus és rekurzív szerkezetük ([[Cayley-gráf]]ok, ezért [[csúcstranzitív gráf|csúcstranzitívek]]), szublogaritmikus fokszámmal és átmérővel rendelkeznek és relatíve [[sűrű gráf|ritkák]] (pl. a [[hiperkockagráf]]okhoz képest), ezért  a [[permutáló csillaggráf]]ok mellett a párhuzamos számítógépek hálózati összeköttetéseinek modelljeként komoly érdeklődés tárgyát képezik.<ref name="ongenus"/><ref>{{Cite journal|last=Akl|first=S.G.|last2=Qiu|first2=K.|last3=Stojmenović|first3=I.|date=1993|title=Fundamental algorithms for the star and pancake interconnection networks with applications to computational geometry.|url=http://onlinelibrary.wiley.com/doi/10.1002/net.3230230403|journal=Networks|volume=23|issue=4|pages=215–225|doi=10.1002/net.3230230403}}</ref><ref>{{Cite journal|last=Bass|first=D.W.|last2=Sudborough|first2=I.H.|date=2003-03|title=Pancake problems with restricted prefix reversals and some corresponding Cayley networks.|url=http://dx.doi.org/10.1016/S0743-7315(03)00033-9|journal=Journal of Parallel and Distributed Computing |volume=63|issue=3|pages=327–336|doi=10.1016/S0743-7315(03)00033-9}}</ref><ref>{{Cite journal|last=Berthomé|first=P.|last2=Ferreira|first2=A.|last3=Perennes|first3=S.|date=1996-12|title=Optimal information dissemination in star and pancake networks.|url=http://ieeexplore.ieee.org/document/553290/|journal=IEEE Transactions on Parallel and Distributed Systems|volume=7|issue=12|pages=1292–1300|doi=10.1109/71.553290}}</ref> Hálózati összeköttetések modelljeként tekintve a palacsintagráfokra, a gráf átmérője a kommunikációs késleltetést reprezentálja.<ref>Kumar, V., Grama, A., Gupta, A., Karypis, G.: Introduction to Parallel Computing: Design and Analysis of Algorithms. Benjamin/Cummings (1994)</ref><ref>Quinn, M.J.: Parallel Computing: Theory and Practice, second edition. McGrawHill (1994)</ref>

==Kapcsolódó sorozatok==
:{| class="wikitable" align="center" style="float: center; text-align: right;"
|+ Adott {{math|''n''}} magasságú oszlopok száma, melyek rendezése {{math|''k''}}&nbsp;átfordítást igényel
! rowspan=2 | Magasság<br />{{math|''n''}} !! colspan=16 | {{math|''k''}}
|-
! width="65px" |  0 !! width="65px" |  1 !! width="65px" |  2 !! width="65px" |  3 !! width="65px" |  4 !! width="65px" |  5 !! width="65px" |  6 !! width="65px" | 7 
! width="65px" |  8 !! width="65px" |  9 !! width="65px" | 10 !! width="65px" | 11 !! width="65px" | 12 !! width="65px" | 13 !! width="65px" |  14 !! width="65px"|15
|-
! 1
| 1 || || || || || || || || || || || || || || ||
|-
! 2
| 1 || 1 || || || || || || || || || || || || || ||
|-
! 3
| 1 || 2 || 2 || 1 || || || || || || || || || || || ||
|-
! 4
| 1 || 3 || 6 || 11 || 3 || || || || || || || || || || ||
|-
! 5
| 1 || 4 || 12 || 35 || 48 || 20 || || || || || || || || || ||
|-
! 6
| 1 || 5 || 20 || 79 || 199 || 281 || 133 || 2 || || || || || || || ||
|-
! 7
| 1 || 6 || 30 || 149 || 543 || 1357 || 1903 || 1016 || 35 || || || || || || ||
|-
! 8
| 1 || 7 || 42 || 251 || 1191 || 4281 || {{szám|10561}} || {{szám|15011}} || 8520 || 455 || || || || || ||
|-
! 9
| 1 || 8 || 56 || 391 || 2278 || {{szám|10666}} || {{szám|38015}} || {{szám|93585}} || {{szám|132697}} || {{szám|79379}} || 5804 || || || || ||
|-
! 10
| 1 || 9 || 72 || 575 || 3963 || {{szám|22825}} || {{szám|106461}} || {{szám|377863}} || {{szám|919365}} || {{szám|1309756}} || {{szám|814678}} || {{szám|73232}} || || || ||
|-
! 11
| 1 || 10 || 90 || 809 || 6429 || {{szám|43891}} || {{szám|252737}} || {{szám|1174766}} || {{szám|4126515}} || {{szám|9981073}} || {{szám|14250471}} || {{szám|9123648}} || {{szám|956354}} || 6 || ||
|-
! 12
| 1 || 11 || 110 || 1099 || 9883 || {{szám|77937}} || {{szám|533397}} || {{szám|3064788}} || {{szám|14141929}} || {{szám|49337252}} || {{szám|118420043}} || {{szám|169332213}} || {{szám|111050066}} || {{szám|13032704}} || 167 ||
|-
! 13
| 1 || 12 || 132 || 1451 || {{szám|14556}} || {{szám|130096}} || {{szám|1030505}} || {{szám|7046318}} || {{szám|40309555}} || {{szám|184992275}} || {{szám|639783475}} || {{szám|1525125357}} || {{szám|2183056566}} || {{szám|1458653648}} || {{szám|186874852}} || 2001
|}

[[On-Line Encyclopedia of Integer Sequences|OEIS]]-sorozatok a témában:
* {{OEIS2C|A058986}} – maximális szükséges átfordítások száma
* {{OEIS2C|A067607}} – a maximális átfordítást igénylő oszlopok száma (lásd fent)
* {{OEIS2C|A078941}} – maximális szükséges átfordítások száma az „égetett” esetben
* {{OEIS2C|A078942}} – szükséges átfordítások száma a rendezett „égetett oldal felül” oszlopnál
* {{OEIS2C|A092113}} – a fenti háromszög, soronként kiolvasva.

==Megvalósítása==
{{rejtett eleje|title=C#|ta1=left}}
<syntaxhighlight lang="C#">
public static void PancakeSort<T>(IList<T> arr, int cutoffValue = 2)
	where T : IComparable
{
	for (int i = arr.Count - 1; i >= 0; --i)
	{
		int pos = i;
		// Find position of max number between beginning and i
		for (int j = 0; j < i - 1; j++)
		{
			if (arr[j].CompareTo(arr[pos]) > 0)
			{
				pos = j;
			}
		}

		// is it in the correct position already? 
		if (pos == i)
		{
			continue;
		}

		// is it at the beginning of the array? If not flip array section so it is
		if (pos != 0)
		{
			Flip(arr, pos + 1);
		}

		// Flip array section to get max number to correct position    
		Flip(arr, i + 1);
	}
}

private static void Flip<T>(IList<T> arr, int n)
	where T : IComparable
{
	for (int i = 0; i < n; i++)
	{
		--n;
		T tmp = arr[i];
		arr[i] = arr[n];
		arr[n] = tmp;
	}
}
</syntaxhighlight>
{{Hidden end}}

==Fordítás==
* {{fordítás|en|Pancake sorting|oldid=792872347|n=a|4=angol}}

==Jegyzetek==
{{Reflist}}

==Irodalom==
* Heydari, M. H. and Sudborough, I. H. "On the Diameter of the Pancake Network," ''Journal of Algorithms'' '''25''' (1), 67-94, 1997.
* Roney-Dougal, C. and Vatter, V. "[http://plus.maths.org/issue54/features/colvatter/ Of pancakes, mice and men]," ''Plus Magazine'' '''54''', March 2010.
* Chitturi, B.  and Sudborough, H. "Prefix reversals on strings". Proc. Int. Conf. Bioinformatics and Computational Biology, Vol. 2 (2010)591–598.
* Hurkens, C., Iersel, L. V., Keijsper, J., Kelk,  S., Stougie, L. and Tromp J. "Prefix reversals on binary and ternary strings".  SIAM J. Discrete Math. 21(3)(2007) 592–611.

==További információk==
* [http://www.cut-the-knot.org/SimpleGames/Flipper.shtml Cut-the-Knot: Flipping pancakes puzzle], including a Java applet for the pancake problem and some discussion.
* [http://www.math.uiuc.edu/~west/openp/pancake.html Douglas B. West's "The Pancake Problems"]
* {{MathWorld |urlname=PancakeSorting |title=Pancake Sorting}}
* [https://web.archive.org/web/20120212231352/http://www.bio.davidson.edu/people/kahaynes/FAMU_talk/Living_computer.swf Animation explaining the bacterial computer that can solve the burnt pancake problem.]
* [https://web.archive.org/web/20140607001227/http://arkaroychowdhury1.wordpress.com/2014/06/02/tower1/ "Tower1/Pancake Flip" by Arka. A game based on pancake problem principle]

[[Kategória:Rendezési algoritmusok]]