Penyortiran panekuk

Penyortiran panekuk adalah variasi masalah penyortiran yang satu-satunya operasi yang diperbolehkan adalah membalikkan elemen sejumlah prefiks urutan. Tidak seperti algoritma penyortiran lama, yang berusaha mengurutkan dengan perbandingan sesedikit mungkin, tujuan penyortiran ini adalah mengurutkan sebuah urutan dengan pembalikan sesedikit mungkin. Operasi ini dapat divisualisasikan dengan membayangkan tumpukan panekuk dan seseorang dibolehkan mengambil panekuk k di atas dan membalikannya. Ada satu varian masalah ini yang berkaitan dengan panekuk gosong, yaitu ketika setiap panekuk memiliki sisi gosong dan semua panekuk harus berakhir dengan sisi gosong di atasnya.

Demonstrasi operasi primer. Spatula sedang membalikkan tiga panekuk teratas, dengan hasilnya terlihat di bawah. Dalam masalah panekuk gosong, sisi atasnya akan terbakar, bukan sisi bawahnya.

Referensi

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.

Chitturi, B. "A note on complexity of genetic mutations". DMAA 3(3) (2011)269-286 DOI:10.1142/S1793830911001206.

Bacaan lanjutan

• Mohammad, H.H. and Hal Sudborough, I. "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.

Pranala luar

• Cut-the-Knot: Flipping pancakes puzzle, including a Java applet for the pancake problem and some discussion.
• Douglas B. West's "The Pancake Problems"
• (Inggris) Weisstein, Eric W. "Pancake Sorting". MathWorld. 
• Animation explaining the bacterial computer that can solve the burnt pancake problem.