Penyortiran panekuk

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.

Penyortiran panekuk adalah variasi masalah penyortiran yang satu-satunya operasi yang diperbolehkan adalah membalikkan elemen sejumlah prefiks urutan. Tidak seperti algoritme 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.

Referensi

Bacaan lanjutan

Chitturi, B.; Sudborough, H. (2010). "Prefix Reversals on Strings". Proceedings of the International Conference on Bioinformatics & Computational Biology. 2: 591–598.
Chitturi, B. (2011). "A Note on Complexity of Genetic Mutations". Discrete Math. Algorithm. Appl. 3 (3): 269–287. doi:10.1142/S1793830911001206.
Heydari, M. H.; Sudborough, I. H. (1997). "On the Diameter of the Pancake Network". Journal of Algorithms. 25 (1): 67–94. doi:10.1006/jagm.1997.0874.
Hurkens, C.; van Iersel, L.; Keijsper, J.; Kelk, S.; Stougie, L.; Tromp, J. (2007). "Prefix Reversals on Binary and Ternary Strings". SIAM Journal on Discrete Mathematics. 21 (3): 592–611. arXiv:math/0602456. doi:10.1137/060664252.
Roney-Dougal, C.; Vatter, V. (March 2010). "Of Pancakes, Mice and Men". Plus Magazine. 54.

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.