對堆棧中的數字序列進行排序所需的最小操作數

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

我想你是在談論着名的煎餅排序算法。

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），之後我的算法在兩個步驟中得到正確的順序。我不確定這是否一般。