Palacsintarendezés

A Wikipédiából, a szabad enciklopédiából
Ugrás a navigációhoz Ugrás a kereséshez
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ű 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.[1] 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[szerkesztés]

Az eredeti palacsintaprobléma[szerkesztés]

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)
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 n 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.[2]

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[3] 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.[4] (Chitturi et al., 2009[5]).

2011-ben Laurent Bulteau, Guillaume Fertin és Irena Rusu[6] 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[szerkesztés]

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á).[7]

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.[8]

Égetett palacsinta-számok
(A078941 sorozat az OEIS-ben)
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[szerkesztés]

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.[9]

A palacsintaprobléma karakterláncokon[szerkesztés]

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[10] (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[szerkesztés]

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.[11][12]

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.[3] Ráadásul a Futurama társszerzője, David X. Cohen (mint David S. Cohen) is foglalkozott az égetett palacsinta-problémával.[13]

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

Palacsintagráfok[szerkesztés]

A P3 palacsintagráf
A P4 palacsintagráf rekurzívan előállítható a P3 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 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.[17]

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:[18]

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.[18][19][20][21] 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.[22][23]

Kapcsolódó sorozatok[szerkesztés]

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:

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

Megvalósítása[szerkesztés]

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[szerkeszté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.

Jegyzetek[szerkesztés]

  1. Simon Singh. „Flipping pancakes with mathematics”, 2013. november 14. (Hozzáférés ideje: 2014. március 25.) 
  2. Fertin, G. and Labarre, A. and Rusu, I. and Tannier, E. and Vialette, S.. Combinatorics of Genome Rearrangements. The MIT Press (2009). ISBN 9780262062824 
  3. a b Gates, W. (1979). „Bounds for Sorting by Prefix Reversal”. Discrete Mathematics 27, 47–57. o. [2007. június 10-i dátummal az eredetiből archiválva]. DOI:10.1016/0012-365X(79)90068-2. (Hozzáférés ideje: 2017. július 30.)  
  4. Team Bests Young Bill Gates With Improved Answer to So-Called Pancake Problem in Mathematics. University of Texas at Dallas News Center, 2008. szeptember 17. (Hozzáférés: 2008. november 10.) „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.”
  5. Chitturi, B. (2009. augusztus 31.). „An (18/11)n upper bound for sorting by prefix reversals”. Theoretical Computer Science 410 (36), 3372–3390. o. DOI:10.1016/j.tcs.2008.04.045.  
  6. „Pancake Flipping Is Hard”. Journal of Computer and System Sciences 81, 1556–1574. o. DOI:10.1016/j.jcss.2015.02.003.  
  7. 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.
  8. (2008) „Engineering bacteria to solve the Burnt Pancake Problem”. Journal of Biological Engineering 2, 8. o. DOI:10.1186/1754-1611-2-8. PMID 18492232.  
  9. https://arkaroychowdhury1.wordpress.com/portfolio/flippingpancakes/
  10. „A NOTE ON COMPLEXITY OF GENETIC MUTATIONS”. Discrete Mathematics, Algorithms and Applications 03 (03). DOI:10.1142/S1793830911001206.  
  11. (1993) „Fault tolerant routing in the star and pancake interconnection networks”. Information Processing Letters 45 (6), 315–320. o. DOI:10.1016/0020-0190(93)90043-9.  .
  12. Proceedings of Seventh International Conference on Parallel and Distributed Computing, Applications and Technologies, 2006 (PDCAT '06), 254–259. o.. DOI: 10.1109/PDCAT.2006.56 (2006). ISBN 0-7695-2736-1 .
  13. (1995) „On the problem of sorting burnt pancakes”. Discrete Applied Mathematics 61 (2), 105. o. DOI:10.1016/0166-218X(94)00009-3.  
  14. 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.
  15. Berman, P. and Karpinski, M. "On Some Tighter Inapproximability Results." Proc. 26th ICALP (1999), LNCS 1644, Springer, 200-209, 1999.
  16. 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.
  17. Asai, Shogo (2006. szeptember 1.). „Computing the Diameter of 17-Pancake Graph Using a PC Cluster.”. Euro-Par 2006 Parallel Processing: 12th International Euro-Par Conference. DOI:10.1007/11823285_117.  
  18. a b Nguyen, Quan (2009. november 5.). „On the Genus of Pancake Network.”. The International Arab Journal of Information Technology 8 (3), 289–292. o.  
  19. Akl, S.G. (1993. november 14.). „Fundamental algorithms for the star and pancake interconnection networks with applications to computational geometry.”. Networks 23 (4), 215–225. o. DOI:10.1002/net.3230230403.  
  20. Bass, D.W. (2003. március 1.). „Pancake problems with restricted prefix reversals and some corresponding Cayley networks.”. Journal of Parallel and Distributed Computing 63 (3), 327–336. o. DOI:10.1016/S0743-7315(03)00033-9.  
  21. Berthomé, P. (1996. december 1.). „Optimal information dissemination in star and pancake networks.”. IEEE Transactions on Parallel and Distributed Systems 7 (12), 1292–1300. o. DOI:10.1109/71.553290.  
  22. Kumar, V., Grama, A., Gupta, A., Karypis, G.: Introduction to Parallel Computing: Design and Analysis of Algorithms. Benjamin/Cummings (1994)
  23. Quinn, M.J.: Parallel Computing: Theory and Practice, second edition. McGrawHill (1994)

Irodalom[szerkesztés]

  • 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[szerkesztés]