1

セット{1,2、...、n}の順列が与えられます。私はこの順列を、最小の総コストで連続した位置にある番号を交換することによってのみソートする必要があります。連続した位置にある要素x、yを交換するコストは、min（x、y）です。

たとえば、順列3,1,2,4がある場合、最小コストの合計は3です。これらの手順を実行するため（（x、y）はxをyと交換することを意味します）：

  • （3,1）、2,4の結果は1,3,2,4で、コストはmin（1,3）=1です。
  • 1、（3,2）、4の結果は1,2,3,4で、コストはmin（2,3）=2です。

総費用は3です。

ソートされていないペアがなくなるまで、最小コストのソートされていないペアを交換することでブルートフォースを試しましたが、この方法は明らかに十分な速度ではありません。

私の質問は、自分の条件を考慮して、ソートの最小コストをどのように見つけるかです。

4

2 に答える 2

5

シーケンスをソートするための連番スワップの数は、逆順のペアの数に等しくなります。

例えば

6 1 3 2 4 5

逆順のペアを以下に示します。

(6,1) (6,3) (6,2) (6,4) (6,5) (3,2)

それで

シーケンスをソートする操作は次のとおりです。

swap(6,1) 1 6 3 2 4 5
swap(6,3) 1 3 6 2 4 5
swap(6,2) 1 3 2 6 4 5
swap(6,4) 1 3 2 4 6 5
swap(6,5) 1 3 2 4 5 6
swap(3,2) 1 2 3 4 5 6

したがって、操作は決定的です（無駄な操作を行わない限り）。

すべてのペア (x,y) を逆順に数え、min(x,y) を合計するだけです。

于 2012-05-11T15:06:30.327 に答える
1

このアルゴリズムは挿入ソートのように聞こえます。順列の反転を排除することに基づく挿入ソート。そして、あなたの仕事は、挿入ソートのように反転を排除することです。ご存知のように、並べ替えられた配列には反転がありません。

挿入ソート アルゴリズムの時間計算量は O(n+d) です。ここで、n は要素の数、d - は反転の数です。

順列の反転の最大数は n*(n-1)/2 で、最小値は 0 です。

修正マージソートを使用して、配列内の反転の数を O(n*lg n) で見つけることができます。

于 2012-05-11T15:01:35.673 に答える