主題
Search

煎餅排序


假設有 n 個編號的煎餅堆疊在一起,並且可以使用鏟子反轉頂部 k 個煎餅的順序,其中 2<=k<=n。那麼,煎餅排序問題詢問需要多少次這樣的“字首反轉”才能對任意堆疊進行排序(Skiena 1990, p. 48)。

對隨機堆疊的 n=1, 2, 3, ... 個煎餅進行排序所需的最大翻轉次數 a_n 為 0, 1, 3, 4, 5, 7, 8, 9, 10, 11, 13, ... (OEIS A058986),其中 n=2, 3, ... 個煎餅的最大堆疊數為 1, 1, 3, 20, 2, 35, 455, ... (OEIS A067607)。

PancakeSortingBinaryPlot

下表 (OEIS A092113) 給出了對 n 個煎餅進行排序需要 k 次翻轉的堆疊數量。上面顯示了一個扁平化版本,以 二元圖 的形式展示。

n\k012345678
11
211
31221
4136113
51412354820
61520791992811332
7163014954313571903101635
PancakeSorting4

例如,需要最多四次翻轉的四個煎餅的三種堆疊方式是 (2,4,1,3)(3,1,4,2)(4,2,3,1),它們可以使用翻轉序列 (2,4,3,2)(2,3,4,2)(2,3,2,4) 分別進行排序(如上圖所示)。類似地,需要最多七次翻轉的六個煎餅的兩種堆疊方式是 (4,6,2,5,1,3)(5,3,6,1,4,2),它們可以使用翻轉序列 (2,3,4,2,6,3,2)(2,3,6,2,4,3,2) 分別進行排序。

已知對於 n>=6a_n>=n+1 成立;如果 n 是 16 的倍數,則 a_n>=17n/16 成立;並且 a_n<=(5n+5)/3 成立。


另請參閱

煎餅定理, 漢諾塔

使用 探索

參考文獻

Berman D. and Klamkin, M. S. "A Reverse Card Shuffle." SIAM Rev. 19, 739-741, 1977.Cohen D. S. and Blum, M. "On the Problem of Sorting Burnt Pancakes." Discr. Appl. Math. 61, 105-120, 1995.Dweighter, H. "Problem E2569." Amer. Math. Monthly 82, 1010, 1975.Garey, M. R.; Johnson, D. S.; and Lin, S. Amer. Math. Monthly 84, 296, 1977.Gates, W. and Papadimitriou, C. "Bounds for Sorting by Prefix Reversal." Discr. Math. 27, 47-57, 1979.Györi, E. and Turán, G. "Stack of Pancakes." Studia Sci. Math. Hungar. 13, 133-137, 1978.Heydari M. H. and Sudborough, I. H. "On the Diameter of the Pancake Network." J. Algorithms 25, 67-94, 1997.Morales L. and Sudborough, I. H. "A Quadratic Lower Bound for Reverse Card Shuffle." Presented at 26th S.E. Conf. Comb. Graph Th. Computing. Preprint 1995.Pegg, E. Jr. "Pancake Sequence." http://www.mathpuzzle.com/pancakes.htm.Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, 1990.Sloane, N. J. A. "My Favorite Integer Sequences." In Sequences and Their Applications (Proceedings of SETA '98) (Ed. C. Ding, T. Helleseth, and H. Niederreiter). London: Springer-Verlag, pp. 103-130, 1999. http://www.research.att.com/~njas/doc/sg.pdf.Sloane, N. J. A. Sequences A058986, A067607, and A092113 in "The On-Line Encyclopedia of Integer Sequences."West, D. B. "The Pancake Problems (1975, 1979, 1973)." http://www.math.uiuc.edu/~west/openp/pancake.html.

在 中被引用

煎餅排序

請這樣引用

Weisstein, Eric W. “煎餅排序。” 來自 —— 資源。 https://mathworld.tw/PancakeSorting.html

主題分類