Palacsintarendezés

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 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 palacsintaproblémák

Az eredeti palacsintaprobléma

Hat palacsintából álló oszlop. Az {5 ; 3 ; 6 ; 1 ; 4 ; 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 ; 6 ; 2 ; 5 ; 1 ; 3}).

Palacsintaszámok
(A058986 sorozat az OEIS-ben)

$n$	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17
$P_{n}$	0	1	3	4	5	7	8	9	10	11	13	14	15	16	17	18	19

Az n palacsintát tartalmazó oszlop rendezéséhez mindig elégséges, minimális átfordítások száma ${\frac {15}{14}}n$ és ${\frac {18}{11}}n$ (kb. $1,07n$ és $1,64n$) között van, de a pontos érték nem ismert.

A legegyszerűbb palacsintarendező algoritmusnak $2n-3$ 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 ${\frac {5}{3}}n$ felső korlátot igazolt. Ezt 30 évvel később ${\frac {18}{11}}n$-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: $3n/2\leq P'_{n}\leq 2n-2$ (ahol a felső korlát csak $n>9$-től válik igazzá).

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
(A078941 sorozat az OEIS-ben)

$n$	1	2	3	4	5	6	7	8	9	10	11	12
$P'_{n}$	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.

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, az előjel nélkülinek még bizonyos konstans faktorral történő közelítése is nehéznek bizonyult, bár polinom időben közelíthetőnek bizonyult 1,375-ös approximációs faktorral.

Palacsintagráfok

A P₃ palacsintagráf

A P₄ palacsintagráf rekurzívan előállítható a P₃ 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_n 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, P_n rekurzívan előállítható a P_n−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 P_n palacsintagráf reguláris, csúcsainak száma n!, fokszáma n−1. Girthparamétere:

$g(P_{n})=6{\text{, ha }}n>2$.

A P_n palacsintagráf γ(P_n) génuszáról elmondható, hogy:

$n!\left({\frac {n-4}{6}}\right)+1\leq \gamma (P_{n})\leq n!\left({\frac {n-3}{4}}\right)-{\frac {n}{2}}+1$

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.

Kapcsolódó sorozatok

Adott n magasságú oszlopok száma, melyek rendezése k átfordítást igényel

Magasság n	k
	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	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	10 561	15 011	8520	455
9	1	8	56	391	2278	10 666	38 015	93 585	132 697	79 379	5804
10	1	9	72	575	3963	22 825	106 461	377 863	919 365	1 309 756	814 678	73 232
11	1	10	90	809	6429	43 891	252 737	1 174 766	4 126 515	9 981 073	14 250 471	9 123 648	956 354	6
12	1	11	110	1099	9883	77 937	533 397	3 064 788	14 141 929	49 337 252	118 420 043	169 332 213	111 050 066	13 032 704	167
13	1	12	132	1451	14 556	130 096	1 030 505	7 046 318	40 309 555	184 992 275	639 783 475	1 525 125 357	2 183 056 566	1 458 653 648	186 874 852	2001

OEIS-sorozatok a témában:

•  A058986 – maximális szükséges átfordítások száma
•  A067607 – a maximális átfordítást igénylő oszlopok száma (lásd fent)
•  A078941 – maximális szükséges átfordítások száma az „égetett” esetben
•  A078942 – szükséges átfordítások száma a rendezett „égetett oldal felül” oszlopnál
•  A092113 – a fenti háromszög, soronként kiolvasva.

Megvalósítása

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

Fordítás

• Ez a szócikk részben vagy egészben a Pancake sorting című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

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"
• Weisstein, Eric W.: Pancake Sorting (angol nyelven). Wolfram MathWorld
• Animation explaining the bacterial computer that can solve the burnt pancake problem.
• "Tower1/Pancake Flip" by Arka. A game based on pancake problem principle