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

あなたは有名なパンケーキの並べ替えアルゴリズムについて話していると思います。

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を検討するとき、それはすでに適切な場所にあるか、最後にあります。最悪の場合、終了するにはもう1回反転する必要があります。これにより、2N-3が得られます。

いくつかの固有の順序を利用すると、特定のシーケンスに対してより良い結果が得られる可能性があります。要素の「順序」を最大化する最初のステップが良いかもしれないという予感があります。つまり、「すべての要素が左側に小さい要素の数」が最大になるように最初のステップを実行します。たとえば、から始めて43215、最初の完全な反転は51234（注文番号= 3）を与え、その後、私のアルゴリズムはたった2つのステップで正しい順序を取得します。これが一般的かどうかはわかりません。