是否有任何递归公式给出排列数，每个排列都可以通过使用煎饼排序算法对 n 个煎饼进行一定次数的翻转而减少为有序排列？
最佳答案
我没有证据，但愿意花大笔钱打赌没有这样的证据，除非你将翻转的次数限制在很小的范围内。
递归计算有多少种执行翻转操作的方法没有问题。挑战在于弄清楚还有多少其他方法可以通过不同的翻转顺序达到相同的顺序。事实上每https://en.wikipedia.org/wiki/Pancake_sorting#The_pancake_problems ，找到到达特定顺序的最短翻转序列是 NP-hard。这意味着，如果您有多次翻转，则用于识别何时有另一个翻转的适当表达式将会出现组合爆炸。
如果您想要可以通过 n 中的选择排序算法撤消的排列步骤，有一种方法可以以适合动态规划的方式递归计算它。
让f(n, m, on_top)是可以在 n 中解决的排列数步骤，用 m是最大的一个，并且on_top是一个变量，表示最大的不合适的是否在堆栈的顶部。作为一个特例，我们会说 f(0, 0, True) = 1表示不需要排序的排序堆栈。
现在我们的递归规则如下:
- 基本案例:
f(0, 0, True) = 1 - 第二种基本情况:如果
0 < n然后f(n, 0, False) = f(n, 0, True) = 0 - 第三个基本案例:如果
0 < m然后f(0, m, True) = f(0, m, False) = 0 - 我们将最大的放在最上面的案例:
f(n, m, False) = (m-2) * f(n-1, m, True).之所以会这样，是因为m煎饼必须在最上面m-1位置，因为它不合适并且没有更大的东西流离失所。但它不能在顶部，因为最后一个参数将是True但事实并非如此。这样就给出了m-2我们必须做的可能的翻转。 - 我们将最大的放在它的位置的案例:
f(n, m, True) = sum over i < m of (f(n-1, i, False) + f(n-1, i, True)).这只是我们翻转以将最大的放在它的位置，然后拿出下一个最大的不合适的地方。
这足以让我们编写一个递归函数来计算答案。不幸的是，天真地计算该函数将涉及很多 重复调用。但是，如果我们 memoize此函数通过保存您为一组参数获得的值并在下次再次返回它来实现，然后您将短路大部分计算并评估它只需要多项式的工作量。
关于algorithm - 给出排列数的递归公式？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/53398303/