なぜこのシャッフルアルゴリズムが間違っていますか？

Question

私はフィッシャーイエーツについて読む前に、これは私が思いついたアルゴリズムです：私の理解から

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

は、これとフィッシャー・イエーツとの唯一の違いは、代わりに：

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

私は書く必要があります：

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

誰かが最初のアルゴリズムが間違っていることを説明できますか？ （すなわちランダムなシャッフルを生成しません）。ウィキペディアから

Answer 1

は：

同様に、各反復で有効な配列インデックスの全範囲から常に選択jはまた、明らかにそう少ないにもかかわらず、バイアスされた結果を生成します。これは、そうすることによってスワップの可能な異なるシーケンスが得られるという事実から見ることができるが、n！ n要素配列の可能な順列。 n ⁿは、nで割り切れることは決してありません。 n> 2の場合（後者はnとの素因数を共有しないn-1で割り切れるので）、スワップのシーケンスの多くが他のものよりも多くの置換によって生成されなければならない。このバイアスの具体例として、3要素アレイのシャフリングの可能な結果の分布を観察する[1,2,3]。この配列には6つの可能な順列（3！= 6）がありますが、アルゴリズムは27通りのシャッフル（33 = 27）を生成します。この場合、[1,2,3]、[3,1,2]、および[3,2,1]はそれぞれ27個のシャッフルのうちの4個から得られ、残りの3個の置換の各々は27個のうちの5個シャッフル。

本質的に、シャッフルに微妙な偏りを導入しています。これにより、ある種の順列が他のものより少し頻繁に切り抜かれることになります。多くの場合それほど目立つことはありませんが、敏感なアプリケーション（例：順列に関するモンテカルロシミュレーション）が正確な回答を生成できないことがあります。