4

全体の順序付けが存在する要素の配列があるとしましょう。バブル ソート距離は、バブル ソートを使用した場合に配列をソートするために必要なスワップの数です。事前に指定された数値以下のバブルソート距離を持つこの配列の可能な順列の数を計算する効率的な (おそらく動的プログラミングを伴う) 方法は何ですか?

問題を単純化する場合は、配列のすべての要素が一意である (関係がない) と想定できます。

4

2 に答える 2

2

わかりました、ここに解決策があります。配列のすべての要素が個別であると仮定しましょう。さらに、一般性を失うことなく、{1,...,n} であると仮定できます。(要素のラベルをいつでも変更できるので、これが事実であり、何も影響を受けません。)

まず、バブル ソートによって実行されるスワップの数は、順列 a[1..n]の反転の数であることがわかります。つまり、i<j but a[i]> となるペア (i,j) の数です。 [j]。(これを証明するのはそれほど難しくありません。)

したがって、{1,...,n} の順列の数と最大 k 回の反転が必要です。c(n,k) がこの数を表すとします。{1,...n} の順列は、{1,...,n-1} の順列を取り、そのどこかに {n} を挿入するものと考えることができます。位置 i に挿入すると、正確に ni 個の新しい反転が作成されます。したがって、古い順列には最大で k-(ni) 反転が含まれていたに違いありません。これは与える：

c(n,k) = sum_{i s.t. n-i≤k} c(n-1, k-(n-i))
       = sum_{i=max(1,n-k) to n} c(n-1, k-n+i)

そして基本ケース：

c(1,0) = 1 (or better, c(0,0)=1)

(k は最大でも n*(n-1)/2 < n 2であることに注意してください。)

更新：上記はO（n ^ 2k）かかります—つまり、最大O（n ^ 4）— c（n、k）を計算するのに時間がかかります。これは、nk c（n、k）のそれぞれにO（n）時間がかかるためです以前のものを考慮して計算します。各 c(n,k) を O(1) 時間で計算できるように、再帰を短くすることで n 倍改善できます。k-n+i を j と書き、

c(n,k) = sum_{j=max(k-n+1,0) to k} c(n-1, j)

合計の大部分は c(n,k) と c(n,k-1) で同じであることに注意してください。具体的には、

When k≤n-1, c(n,k) = c(n,k-1) + c(n-1,k)
When k≥n,   c(n,k) = c(n,k-1) + c(n-1,k) - c(n-1,k-n)

更新されたプログラム: (私は怠惰なメモ化されたバージョンを書きました。動的プログラミングの通常の方法であるボトムアップにすることで、少し効率を上げることができます。)

ct = {(0,0): 1}
def c(n,k):
    if k<0: return 0
    k = min(k, n*(n-1)/2) #Or we could directly return n! if k>=n*(n-1)/2
    if (n,k) in ct: return ct[(n,k)]
    ct[(n,k)] = c(n,k-1) + c(n-1,k) - c(n-1,k-n)
    return ct[(n,k)]

if __name__ == "__main__":
    n = input("Size of array: ")
    k = input("Bubble-sort distance at most: ")
    print c(n,k)
于 2009-06-04T15:29:25.200 に答える
1

編集距離のWagner-Fisher アルゴリズムを見てください。あなたはおそらく同じ方向に向かっているでしょう: 左上から右下にテーブルを構築できる不変の関係を使用して、問題で n×n になるはずの最小スワップのテーブルを構築します。

于 2009-06-04T03:41:52.067 に答える