algorithm - 对堆栈中的数字序列进行排序所需的最小操作数

Question

我们在堆栈中有 N 个数字，我们希望以最少的操作数对它们进行排序。唯一可用的操作是反转堆栈顶部的最后 K 个数字（K 可以在 2 和 N 之间）。

例如要对序列“2 3 4 5 1”进行排序，我们需要 2 个步骤：

2 3 4 5 1 ---> 1 5 4 3 2 ---> 1 2 3 4 5

是否有任何多项式算法可以找到所需的最小步数？

Answer 1

我想你说的是著名的 Pancake 排序算法。

Quoting from wikipedia : "The maximum number of flips required to sort 
any stack of n pancakes has been shown to lie between (15/14)n and (18/11)n,
but the exact value is not known. The simplest pancake sorting algorithm requires
at most 2n−3 flips. 

In this algorithm, a variation of selection sort, we bring the largest pancake
not yet sorted to the top with one flip, and then take it down to its final 
position with  one more, then repeat this for the remaining pancakes.

Note that we do not count the time needed to find the largest pancake, only the
number of flips; if we wished to create a real machine to execute this algorithm
in linear time, it would have to both perform prefix reversal (flips) and be
able to find the maximum of a range of consecutive numbers in constant time"

Answer 2

可以分 2N-3 步完成（最坏情况）

找到'1'的位置

随机播放到最后（一步）

将其随机播放到开头（反转所有 N）

找到 2 的位置

随机播放到最后

随机播放到开头（倒转最后 N-1 个）

重复...

当你开始考虑元素 N-1 时，它要么已经在正确的位置，要么在最后。在最坏的情况下，您需要再进行一次逆转才能完成。这给了你 2N-3。

当您利用某些内在顺序时，您可以为给定的序列做得更好。我有一种预感，最大化元素“顺序”的初始步骤可能是好的 - 也就是说，执行初始步骤以使“所有元素都小于左侧的元素的数量”最大。例如，从 开始43215，初始完全反转给出51234（订单号 = 3），之后我的算法只需两步即可获得正确的订单。我不确定这是否普遍。