A palacsintarendezés (pancake sorting) az a matematikai probléma, melynek során különböző méretű 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. A 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
+ Palacsintaszámok 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 0 1 3 4 5 7 8 9 10 11 13 14 15 16 17 18 19
Az palacsintát tartalmazó oszlop rendezéséhez mindig elégséges, minimális átfordítások száma és (kb. és ) között van, de a pontos érték nem ismert.
A legegyszerűbb palacsintarendező algoritmusnak 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 felső korlátot igazolt. Ezt 30 évvel később -re javította a University of Texas at Dallas egyetem Hal Sudborough által vezetett kutatócsoportja. (Chitturi et al., 2009).
2011-ben Laurent Bulteau, Guillaume Fertin és Irena Rusu 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: (ahol a felső korlát csak -től válik igazzá).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.
2008-ban egyetemi hallgatók olyan 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 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 (promoterek 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. + Égetett palacsinta-számok 1 2 3 4 5 6 7 8 9 10 11 12 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.https://arkaroychowdhury1.wordpress.com/portfolio/flippingpancakes/
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 (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...
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 Gatesnek (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. Ráadásul a Futurama társszerzője, David X. Cohen (mint David S. Cohen) is foglalkozott az égetett palacsinta-problémával.
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,Kaplan, H., Shamir, R. and Tarjan, R.E. "Faster and Simpler Algorithm for Sorting Signed Permutations by Reversals." Proc. 8th ACM-SIAM SODA (1997), 178-187, 1997. az előjel nélkülinek még bizonyos konstans faktorral történő közelítése is nehéznek bizonyult,Berman, P. and Karpinski, M. "On Some Tighter Inapproximability Results." Proc. 26th ICALP (1999), LNCS 1644, Springer, 200-209, 1999. bár polinom időben közelíthetőnek bizonyult 1,375-ös approximációs faktorral.Berman, P., Karpinski M. and Hannenhalli, S., "1.375-Approximation Algorithms for Sorting by Reversals." Proc. 10th ESA (2002), LNCS 2461, Springer, 200-210, 2002.
Palacsintagráfok
Egy n-palacsintagráf, jelölése Pn 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őjének meghatározása egymással ekvivalens.
Az n méretű palacsintagráf, Pn rekurzívan előállítható a Pn−1 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 Pn palacsintagráf reguláris, csúcsainak száma n!, fokszáma n−1. Girthparamétere:
.
A Pn palacsintagráf γ(Pn) génuszáról elmondható, hogy:
A palacsintagráfok számos érdekes tulajdonsággal rendelkeznek – szimmetrikus és rekurzív szerkezetük (Cayley-gráfok, ezért csúcstranzitívek), szublogaritmikus fokszámmal és átmérővel rendelkeznek és relatíve ritkák (pl. a hiperkockagráfokhoz képest), ezért a permutáló csillaggráfok 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. 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.Kumar, V., Grama, A., Gupta, A., Karypis, G.: Introduction to Parallel Computing: Design and Analysis of Algorithms. Benjamin/Cummings (1994)Quinn, M.J.: Parallel Computing: Theory and Practice, second edition. McGrawHill (1994)
Kapcsolódó sorozatok {| class="wikitable" align="center" style="float: center; text-align: right;" |+ Adott magasságú oszlopok száma, melyek rendezése átfordítást igényel ! rowspan=2 | Magasság !! colspan=16 | |- ! 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 || || || 8520 || 455 || || || || || || |- ! 9 | 1 || 8 || 56 || 391 || 2278 || || || || || || 5804 || || || || || |- ! 10 | 1 || 9 || 72 || 575 || 3963 || || || || || || || || || || || |- ! 11 | 1 || 10 || 90 || 809 || 6429 || || || || || || || || || 6 || || |- ! 12 | 1 || 11 || 110 || 1099 || 9883 || || || || || || || || || || 167 || |- ! 13 | 1 || 12 || 132 || 1451 || || || || || || || || || || || || 2001
OEIS-sorozatok a témában: – maximális szükséges átfordítások száma – a maximális átfordítást igénylő oszlopok száma (lásd fent) – maximális szükséges átfordítások száma az „égetett” esetben – szükséges átfordítások száma a rendezett „égetett oldal felül” oszlopnál – a fenti háromszög, soronként kiolvasva.
Megvalósítása
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;
Fordítás
Jegyzetek
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. "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 Cut-the-Knot: Flipping pancakes puzzle, including a Java applet for the pancake problem and some discussion. Douglas B. West's "The Pancake Problems"
Animation explaining the bacterial computer that can solve the burnt pancake problem. "Tower1/Pancake Flip" by Arka. A game based on pancake problem principle
Kategória:Rendezési algoritmusok