5

fisher yates の最新バージョンは、最も偏りのないシャッフル アルゴリズムだと思いますか? 配列の各要素が 1/n の確率で元の位置にあることをどのように説明しますか?

4

2 に答える 2

8

完全な疑似乱数ジェネレータ ( Mersenne Twisterが非常に近い) が与えられた場合、Fisher-Yates アルゴリズムは、すべての順列の発生確率が等しいという点で完全に偏りがありません。これは帰納法を使えば簡単に証明できます。Fisher-Yates アルゴリズムは、次のように再帰的に記述できます (Python 構文の擬似コード)。

def fisherYatesShuffle(array):
    if len(array) < 2:
        return

    firstElementIndex = uniform(0, len(array))
    swap(array[0], array[firstElementIndex])
    fisherYatesShuffle(array[1:])

各インデックスは、 として選択される確率が等しくなりfirstElementIndexます。再帰すると、まだ残っている要素を選択する確率が等しくなります。

編集:アルゴリズムは数学的に公平であることが証明されています。アルゴリズムは非決定論的であるため、実装が適切に機能するかどうかをテストする最良の方法は、統計的に行うことです。任意だが小さいサイズの配列を取り、それを何度もシャッフルし (毎回入力と同じ順列から開始)、各出力順列が発生する回数をカウントします。次に、ピアソンのカイ 2 乗検定を使用して、この分布の均一性をテストします。

于 2010-03-17T01:14:37.880 に答える
4

（モダン、別名「クヌース」）フィッシャー・イェーツ・シャッフルは

  • 実装が比較的簡単
  • 時間の場合はかなり効率的な O(n)、空間の場合は O(1) または実際には O(0)
  • 偏りがない (すべての順列が等確率である)
  • よく知られている/よく理解され、証明され、テストされています。

アルゴリズムから他に何が必要でしょうか (そうですね、順列の数が膨大になると、別のことを試すかもしれませんが、ほとんどの場合、それほど大きな数は必要ありません) ?

編集: 'この回答は、質問の内容ではなく、質問のタイトルに応答することに気付きました。(これが、質問のこれら 2 つの部分をより適切に一致させることが良い理由です...) 一言で言えば、シャッフルは、アルゴリズムの実装に使用される特定の RNG と同じくらいランダムになります。

直感的な説明は、m 個の要素を持つ配列の場合、たとえ n としてループの減少する制御変数が 1 に向かって減少しても、位置 n のセルが交換される可能性のあるセルが減少し、このセルがまったく同じ割合で増加します。つまり、配列の最後の要素は配列内のどこにでも配置される可能性がありますが、移動される可能性は 1 回だけです (最初の反復時)。最後から 2 番目に移動する要素は移動する場所が 1 つ少なくなりますが、1/m の確率で、最初の反復中にすぐに移動された可能性があります。等

于 2010-03-17T01:13:57.727 に答える