48

私は、同一の数値のない整数シーケンスをソートすることに取り組んでいます (一般性を失うことなく、シーケンスが の順列であると仮定しましょう1,2,...,n) 1,2,...,n。最小数のスワップで要素を直接スワップすることを考えていました (要素の位置に関係なく、つまり、スワップは任意の 2 つの要素に対して有効です) (以下が実行可能な解決策になる可能性があります)。

2 つの要素を、一方または両方を正しい位置にスワップする必要があるという制約でスワップします。すべての要素が正しい位置に配置されるまで。

しかし、上記のソリューションが最適かどうかを数学的に証明する方法がわかりません。誰でも助けることができますか？

4

19 に答える 19

71

これはで証明できました。そのタグを追加したいかもしれません:)

頂点を持つグラフを作成しますn。配置されている要素が正しい順序で配置されている必要がある場合は、ノードn_iからエッジを作成します。これで、いくつかの交差しないサイクルで構成されるグラフが作成されます。グラフを正しく並べ替えるために必要なスワップの最小数はn_jij

M = sum (c in cycles) size(c) - 1

ちょっと考えてみてください... 2 つのアイテムがサイクル内にある場合、1 つのスワップでそれらを処理できます。3 つのアイテムがサイクル内にある場合、ペアを交換して 1 つを適切な場所に配置すると、2 つのサイクルが残ります。アイテムがサイクル内にある場合は、スワップnが必要です。n-1(これは、すぐ近くにあるものとスワップしない場合でも常に当てはまります。)

それを考えると、アルゴリズムが最適である理由を理解できるかもしれません。スワップを実行し、少なくとも 1 つのアイテムが正しい位置にある場合は、常に の値がM1 減ります。 length の任意のサイクルについてn、要素を隣の要素が占める正しい場所にスワップすることを検討してください。これで、正しく順序付けられた要素と長さのサイクルができn-1ました。

Mはスワップの最小数であり、アルゴリズムは常にスワップごとに 1 ずつ減少するためM、最適である必要があります。

于 2013-03-01T07:21:38.380 に答える
3

@Archibald、私はあなたのソリューションが好きです。これは、配列をソートすることが最も簡単なソリューションであるという私の最初の仮定でしたが、私が吹き替えたように逆トラバースの努力をする必要はないと思います。配列を列挙して並べ替え、列挙型のスワップを計算します。

配列の各要素から 1 を引いてから、そのリストをソートするために必要なスワップを計算する方が簡単だと思います

ここに私の微調整/解決策があります:

def swap(arr, i, j):
    tmp = arr[i]
    arr[i] = arr[j]
    arr[j] = tmp

def minimum_swaps(arr):

    a = [x - 1 for x in arr]

    swaps = 0
    i = 0
    while i < len(a):
        if a[i] == i:
            i += 1
            continue
        swap(a, i, a[i])
        swaps += 1

    return swaps

最適性の証明に関しては、@arax には良い点があると思います。

于 2019-10-28T21:39:10.877 に答える
2

// ゼロから始まるシーケンスのみを扱っていると仮定します

function minimumSwaps(arr) {
    var len = arr.length
    var visitedarr = []
    var i, start, j, swap = 0
    for (i = 0; i < len; i++) {
        if (!visitedarr[i]) {
            start = j = i
            var cycleNode = 1
            while (arr[j] != start) {
                j = arr[j]
                visitedarr[j] = true
                cycleNode++
            }
            swap += cycleNode - 1
        }
    }
    return swap
}
于 2018-08-26T15:55:34.963 に答える
1

@bekceによるうまくできたソリューション。C# を使用している場合、変更された配列をセットアップする最初のコードは次のarように簡潔に表現できます。

var origIndexes = Enumerable.Range(0, n).ToArray();
Array.Sort(ar, origIndexes);

次に、コードの残りの部分でorigIndexes代わりに使用します。ar

于 2016-11-22T23:12:13.720 に答える
0

これは、次のシーケンスの順列をソートするためのスワップの最小数を見つける C++ のサンプル コードです。(1,2,3,4,5,.......n-2,n-1,n)

#include<bits/stdc++.h>
using namespace std;


int main()
{
    int n,i,j,k,num = 0;
    cin >> n;
    int arr[n+1];
    for(i = 1;i <= n;++i)cin >> arr[i];
    for(i = 1;i <= n;++i)
    {
        if(i != arr[i])// condition to check if an element is in a cycle r nt
        {
            j = arr[i];
            arr[i] = 0;
            while(j != 0)// Here i am traversing a cycle as mentioned in 
            {             // first answer
                k = arr[j];
                arr[j] = j;
                j = k;
                num++;// reducing cycle by one node each time
            }
            num--;
        }
    }
    for(i = 1;i <= n;++i)cout << arr[i] << " ";cout << endl;
    cout << num << endl;
    return 0;
}
于 2017-01-05T09:47:05.087 に答える
0

JavaScriptで

配列のカウントが 1 から始まる場合

function minimumSwaps(arr) {
   var len = arr.length
    var visitedarr = []
    var i, start, j, swap = 0
    for (i = 0; i < len; i++) {
        if (!visitedarr[i]) {
            start = j = i
            var cycleNode = 1
            while (arr[j] != start + 1) {
                j = arr[j] - 1
                visitedarr[j] = true
                cycleNode++
            }
            swap += cycleNode - 1
        }
    }
    return swap
}

0から始まる入力のelse

function minimumSwaps(arr) {
    var len = arr.length
    var visitedarr = []
    var i, start, j, swap = 0
    for (i = 0; i < len; i++) {
        if (!visitedarr[i]) {
            start = j = i
            var cycleNode = 1
            while (arr[j] != start) {
                j = arr[j]
                visitedarr[j] = true
                cycleNode++
            }
            swap += cycleNode - 1
        }
    }
    return swap
}

現在の HackerEarth 入力用に Darshan Puttaswamy コードを拡張するだけです

于 2019-10-17T10:19:27.100 に答える