10

配列がランダムな順序で指定されている場合、循環ソート配列に変換するために必要な最小数のスワップを出力する必要があります。

たとえば、与えられた配列は 3 5 4 2 1 です

最初のスワップは 5<-->4 結果: 3 4 5 2 1 2 番目のスワップは 2<-->1 結果: 3 4 5 1 2 (最終)

出力: 2

この問題の背後にあるロジックを取得できません。

さらに追加： 隣接する要素間でのみ可能なスワップであり、数値は1からNの範囲です

4

4 に答える 4

5

それが利用可能な最良のアルゴリズムであるかどうかはわかりませんが、O(n^2) ソリューションを考えることができます。

まず、巡回配列の可能性を無視します。もっと単純な問題を解いてみましょう: 配列をソートするためのスワップの最小数はいくつですか。

これはアルゴリズムの並べ替えに関するものではないため、ここで注意してください。比較ベースのソート アルゴリズムの最悪のケースは、少なくともO(n log n)です。この問題では、必要なスワップの最大数は ですn。

なんで？これは、達成できる最大順列サイクル サイズであるためです。必要なスワップの最小数は、順列サイクル サイズから 1 を引いた値です。つまり、配列の任意の順列を順列サイクルとして表すことができます。たとえば、次のようになります。

3 2 1 4 5->(2)(4)(5)(1 3)

サイズ 1 の置換サイクルの場合、スワップは必要ありません。サイズ 2 の順列サイクルでは、ちょうど 1 つのスワップが必要です。これは次のようにスケーリングします。

2 3 4 5 1->(1 2 3 4 5)

この配列がすでに循環ソートされていることを無視すると、この配列は完全にめちゃくちゃになります。通常どおりに並べ替えるには、基本的に 1 を通常の位置に移動する 4 つのスワップが必要です。

順列サイクルの計算は非常に簡単です。配列がソートされている場合、あるべき場所まで数値をたどるだけです。前の例の使用

3 2 1 4 5

  • で始まりA[0]ます。
  • 、および 3 はソートされた配列の 3 番目の要素になるためA[0]==3、3 番目の位置に従います。

  • A[2]==1、および 1 は... であるため、1 番目の位置に続きます。すでにここにいたので、サイズ 2 のサイクルがあります。

  • 次の未訪問位置から再開 (1)

  • A[1]==2は正しい位置にあるので、何もする必要はありません。ここでは、サイズ 1 のサイクルがあります。

  • などなど…

このアルゴリズムは O(n) ですが、可能なすべての位置から始まる配列に対してこれを行う必要があるため (循環しているため)、n 回実行するため、アルゴリズム全体は O(n^2) になります。

アップデート; 私のアルゴリズムを表示するためのいくつかのpythonコード：

def offset_swaps(A, S, offset):
    visited = [False]*len(A)
    swaps = 0

    for i in xrange(len(A)):
        if visited[i]: continue

        cycle, current = 0, i
        while not visited[current]:
            cycle += 1
            visited[current] = True
            current = (S[A[current]] + offset) % len(A)

        swaps += cycle - 1

    return swaps       

def number_of_swaps(A):
    S = {x:i for i,x in enumerate(sorted(A))}
    min_swaps = len(A)
    for i in xrange(len(A)):
        min_swaps = min(min_swaps, offset_swaps(A, S, i))
    return min_swaps

print number_of_swaps((3, 5, 4, 2, 1))
于 2013-03-12T15:26:40.637 に答える
1

ここでのアプローチは、すべての数値をヘルパー配列に並べ替える必要があると思います。次に、巡回シフトごとに、元の配列をこの巡回シフトに取得するために必要なスワップの数を計算します。それらの最小のものを選択してください。

配列 A を配列 B に取得するために必要なスワップの最小数を見つけるには、単純に交換された値の数を数えます (つまり、値 a は値 b の左側にありますが、配列 B ではその逆です)。この問題は、特定の配列の反転をカウントすることと同等であり、修正されたマージ ソートを使用して解決できますO(n*log(n))。

私のアプローチの複雑さはO(n^2*log(n))(サイズ n の配列のすべての巡回シフトに対してマージソートを行うため) です。

あなたの問題に対するより速い解決策は考えられません。

于 2013-03-12T15:23:04.437 に答える
0

仮定:

  1. 配列要素は 1 から N までの整数です。

手順:

  1. 長さ N の 2 番目の (ヒストグラム) 配列 H を割り当てます。
  2. 初期配列 A の 1 回のパスで、インデックス i ごとに H[ (A[i] - i) % N] をインクリメントします。
  3. H の 1 回のパスで、カウントが最大の H の要素 R を特定します。
  4. Hをクリア。
  5. R による回転の下で元の配列内の Orbits の数を識別します (H[i]=0 になるまで H を進めてから、A[i] が回転 R の下のメンバーである軌道をステップスルーすることにより) H を設定します。軌道の各メンバーに対して [i]=1 であり、要素 H[N-1] が処理されるまで繰り返します (軌道の数を数えながら進みます)。A の各要素が 1 回だけアクセスされるため、これも O(N) です。
  6. 必要なスワップ数 = N - オービット。

これがO(N)です。

更新: 複数の軌道を考慮してアルゴリズムを更新しました。各軌道を処理する際に、最後のスワップは 1 つではなく 2 つの要素を配置します。

Orbits の数は、どのような回転でも不変であると思われます。これにより、アルゴリズムが大幅に簡素化されますが、O(N) のままである複雑さには影響しません。

于 2013-03-12T15:52:18.427 に答える
0 
def number_of_swaps(A):
    l=len(A)
    if l < 2:
        return 0
    S1={x:i for i,x in enumerate(A)}
    pos_of_0=S1[0]
    pos_of_N=S1[l-1]
    if pos_of_0 > 0:
        if pos_of_N != (l-1):
            if pos_of_N < pos_of_0:
                n=(pos_of_0+(l-1)-pos_of_N-1)
            else:
                    n=(pos_of_0+(l-1)-pos_of_N)
        else:
            n=(pos_of_0)
    else :
        n=(l-pos_of_N-1)
    A.remove(0)
    A.remove(l-1)
    B=[x-1 for x in A ]
    return n+number_of_swaps(B)

def min_number_of_swaps(A):
    B=sorted(A)
    swaps=[]
    for i in range(len(A)):
        if i == 0:
            C=B
        else:
            C=B[-i:]+B[0:len(A)-i]

        S = {x:i for i,x in enumerate(C)}
        D=[S[i] for i in A]
        swaps.append(number_of_swaps(D))
    return min(swaps)

print min_number_of_swaps([8,5,7,1,2,4,3,6])

7

上記のコードは、問題を解決するための再帰的アプローチです 複雑さ O(N^3)

コードは、最小数のスワップのみを出力するように編集されています。

于 2013-03-16T07:40:58.893 に答える