シャッフルアルゴリズムフェア？ （Javascript）

Question

私はアルゴリズムをJavascriptで配列をシャッフルするために見つけました。 Fisher-Yatesシャッフルとは異なり、forループカウンタで使用可能な「スワップ」の範囲が増えています。これはFisher-Yatesのバージョンがどのように動作するかとは逆のように見えます。私はこれが有効なアルゴリズムかどうか不思議です。それは偽装されたフィッシャー・イェイツですか？それは偏っていますか？

誰かが、それが生成する置換の頻度をテストするためのコードを提供できれば、それはボーナスになります。

<script> 
var shuffle = function (myArray) { 
    var random = 0; 
    var temp = 0; 
    console.log(myArray); 
    for (i = 1; i < myArray.length; i++) { 
     random = Math.round(Math.random() * i); 
     console.log(random + '\n'); 
     temp = myArray[i]; 
     myArray[i] = myArray[random]; 
     myArray[random] = temp; 
     console.log(myArray); 
    } 
    return myArray; 
} 

var arr = [1, 2, 3, 4]; 

shuffle(arr); 

</script> 

Answer 1

いいえ、それは公正なシャッフルではありません。

Math.random() * iは0とi間の一様ランダムな浮動小数点値であるが、等しく0とi間の整数をMath.round(Math.random() * i)選択ありません。たとえば、iが2の場合、範囲[0、0.5]の値は0に丸められ、範囲[0.5,1.5]の値は1に丸められ、範囲（1.5,2）の値は2に丸められます。 0,1,2を等しく頻繁に選ぶのではなく、1を確率0.5で選び、0と2を確率0.25で選びます。

Math.floor(Math.random * (i + 1))となります。

これを統計的に確認することができます。配列[0,1,2]を10000回シャッフルし、配列の最後に2がどれくらいの頻度で残っているかを確認します。それは約3333でなければなりませんが、偏りのため2500ほどのようになります。

それ以外は正しいアルゴリズムで、フィッシャー・イェイツと逆に記述することができます。誘導によって正しいことを証明することができます。 n = 1の基本ケースは自明である。誘導のステップも比較的簡単です：n個のアイテムを一様にランダムに並べ替えた後、n + 1番目のアイテムを0からn + 1まで均一にランダムなインデックスに挿入すると、ランダムn + 1個のアイテムの順列。