9

Fisher-Yates について読む前に、これが私が思いついたアルゴリズムです。

def sort(arr):
    for i in range(len(arr)):
        swap(arr, i, rand.randint(0, len(arr) - 1))

私の理解では、これと Fisher-Yates の唯一の違いは次の点です。

swap(arr, i, rand.randint(0, len(arr) - 1))

私は書くべきです：

swap(arr, i, rand.randint(i, len(arr) - 1))

誰かが最初のアルゴリズムがどのように間違っているか説明できますか? (つまり、ランダムなシャッフルを生成しません)。

4

1 に答える 1

12

ウィキペディアから:

同様に、すべての反復で常に有効な配列インデックスの範囲全体から j を選択すると、あまり明白ではありませんが、偏った結果が生成されます。これは、n! 個しかないのに対し、n 個の異なる可能なスワップ シーケンスが得られるという事実からわかります。n 要素配列の可能な順列。n nは n で割り切れないので! n > 2 の場合 (後者は n −1 で割り切れ、n と素因数を共有しないため)、いくつかの順列はより多くの n nによって生成されなければなりません。他よりもスワップのシーケンス。この偏りの具体例として、3 要素配列をシャッフルした結果の分布を観察してください [1, 2, 3]。この配列には 6 つの可能な順列 (3! = 6) がありますが、アルゴリズムは 27 の可能なシャッフル (3 3 = 27) を生成します。この場合、[1, 2, 3]、[3, 1, 2]、および [3, 2, 1] はそれぞれ 27 回のシャッフルのうち 4 回の結果であり、残りの 3 つの順列はそれぞれ 27 回のうち 5 回で発生します。シャッフルします。

基本的に、シャッフルに微妙なバイアスを導入しているため、一部の順列が他の順列よりも少し頻繁に発生します。多くの場合、あまり目立ちませんが、一部の機密性の高いアプリケーション (順列のモンテカルロ シミュレーションなど) が正確な答えを生成できなくなる可能性があります。

于 2012-08-24T03:50:44.630 に答える