11

要素の順列が与えられ、{1, 2, 3, ..., N}スワップ操作を使用して並べ替える必要があります。要素 x、y を交換する操作のコストは min(x,y) です。

順列の並べ替えの最小コストを見つける必要があります。貪欲にNスワップ1操作を使用して各要素をその位置に配置することについて考えましたが、これは良い考えではありません。

4

5 に答える 5

2

これは最適でしょうか：

Find element 2
If it is not at correct place already

    Find element at position 2
    If swapping that with 2 puts both to right place

        Swap them
        Cost = Cost + min(2, other swapped element)

repeat

   Find element 1
   If element 1 is at position 1

      Find first element that is in wrong place
      If no element found

          set sorted true

      else

         Swap found element with element 1
         Cost = Cost + 1

   else

      Find element that should go to the position where 1 is
      Swap found element with element 1
      Cost = Cost + 1

until sorted is true
于 2012-10-26T17:30:56.293 に答える
1

シークが些細な場合、スワップの最小数はサイクル数によって決まります。Cuckoo Hashingと同様の原則に従います。順列の最初の値を取得し、元のインデックスの値のインデックスの値を調べます。それらが一致する場合は、単一の操作に切り替えます。

[ 3 2 1 ] : 値 3 はインデックス 1 にあるため、インデックス 3 の値を見てください。
[3 2 1 ] : 値 1 はインデックス 3 にあるため、2 つのインデックス サイクルが存在します。これらの値を交換します。

そうでない場合は、最初のインデックスをスタックにプッシュし、2 番目のインデックスの値のインデックスをシークします。最終的にはサイクルが発生します。その時点で、スタックから値をポップしてスワップを開始します。これには、n-1 に等しい数のスワップが必要です。ここで、n はサイクルの長さです。

[ 3 1 2 ] : 値 3 はインデックス 1 にあるので、インデックス 3 の値を見てください。
[3 1 2 ] : 値 2 はインデックス 3 にあるので、スタックに 3 を追加してインデックス 2 にシークします。また、3 を格納します。サイクルの開始値として。
[3 1 2 ] : 値 1 はインデックス 2 にあるため、スタックに 2 を追加し、インデックス 1 をシークします
。1 と 2. [1 3 2] : スタックから 3 を取り出し、2 と 3 を入れ替えて、2 つの入れ替えを含むソート済みリストを作成します。 [1 2 3]

このアルゴリズムでは、スワップの最大数は N-1 になります。ここで、N は値の総数です。これは、長さ N のサイクルがある場合に発生します。

EDIT :このアルゴリズムはスワップの最小数を提供しますが、必ずしも min(x, y) 関数を使用して最小値を提供するわけではありません。計算はしていませんが、swap(x, y) = {swap(1, x), swap(1, y), swap(1, x)} は使用しないでください。 {2,3} の x および n < 2 の場合です。特別なケースとしてそれを書くのは簡単なはずです。2 と 3 を明示的に確認して配置し、コメントに記載されているアルゴリズムに従って、2 つの操作で並べ替えを行う方がよい場合があります。

EDIT 2：これですべてのケースが確実にキャッチされます。

while ( unsorted ) {
    while ( 1 != index(1) )
        swap (1 , index (1) )

    if (index(2) == value@(2))
        swap (2, value@(2) )

    else
        swap (1 , highest value out of place)
}
于 2012-10-26T17:52:58.997 に答える
0

数値 1, 2, ..., Nの順列がある場合、ソートされたコレクションは正確に 1, 2, ..., Nになります。したがって、複雑さ O(0) の答えがわかりました (つまり、アルゴリズムはまったく必要ありません)。

実際にスワップを繰り返して範囲をソートしたい場合は、「前進とサイクル」を繰り返すことができます: すでにソートされている範囲 (ここで) を前進させ、サイクルが完了するまででa[i] == iスワップa[i]します。a[a[i]]最後まで繰り返します。これには最大でN  − 1 回のスワップが必要であり、基本的に順列のサイクル分解を実行します。

于 2012-10-26T16:50:26.983 に答える
0

うーん。興味深い質問です。私の頭に浮かんだ簡単なアルゴリズムは、要素をインデックスとして使用することです。まず、値として 1 を持つ要素のインデックスを見つけ、それをその番号の要素と交換します。最終的に、これは最初の位置に 1 が表示されることになります。これは、まだその位置にない要素と 1 を交換して続行する必要があることを意味します。これは 2*N-2 で最高になり、順列 (2,3,...,N,1) の N-1 で下限がありますが、正確なコストは異なります。

わかりました、上記のアルゴリズムと例を考えると、最も最適なのは、最初に1位になるまで1を何かと交換し、2がまだ配置されていない場合は2位と交換し、1をまだ交換していないものと交換し続けることだと思いますソートされるまで、所定の位置に。

set sorted=false
while (!sorted) {
    if (element 1 is in place) {
        if (element 2 is in place) {
            find any element NOT in place
            if (no element found) sorted=true 
            else {
                swap 1 with element found
                cost++
            }
        } else {
            swap 2 with element at second place
            cost+=2
        }
    } else {
        find element with number equals to position of element 1
        swap 1 with element found
        cost++
    }
}
于 2012-10-26T16:55:36.290 に答える
-1

バケット サイズが 1 のバケット ソートを使用し
ます。スワップが発生しないため、コストはゼロです。次に、バケット配列を通過させ、各値を元の配列内の対応する位置に戻します。
つまり、N スワップです。
N の合計は N(N+1)/2 であり、正確な固定費が得られます。

別の解釈は、バケット配列から元の配列に戻すだけであるということです。これはスワップではないため、コストはゼロであり、妥当な最小値です。

于 2012-10-26T16:57:33.590 に答える