主题
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 成立。


另请参阅

煎饼定理, 汉诺塔

使用 Wolfram|Alpha 探索

参考文献

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.

在 Wolfram|Alpha 中被引用

煎饼排序

请这样引用

Weisstein, Eric W. “煎饼排序。” 来自 MathWorld—— Wolfram Web 资源。 https://mathworld.net.cn/PancakeSorting.html

主题分类