_shuffleのこの実装の背後にあるロジックは何ですか？

Question

誰でもこの実装のバリエーションがどのように機能するかを教えてください。

私たちはのvarランドで（我々がアクセスしようとしているインデックス別名）生成された乱数は、我々は与えられた配列をシャッフルしていることを確認するために、一意であることを確認する方法として、少し困惑しています。

例：生成された乱数が2と3のインデックスを繰り返すために起こったので[3,4,3,1] [3,4,3,1]と[3,3,4,4]は返されません。

_.shuffle = function(array) { 
 
    var newArr = array.slice(); 
 
     for (var i=array.length-1; i>0; i--) { 
 
     var rand = Math.round(Math.random() * i); 
 
     var temp = newArr[rand]; 
 
     newArr[rand] = newArr[i]; 
 
     newArr[i] = temp; 
 
     } 
 
    return newArr; 
 
    };

Answer 1

ranは、一意である必要はありません。

forループの繰り返しごとに、シャッフルアルゴリズムは配列内の2つの項目をスワップします。

このように、ranがユニークでない場合は、2つのアイテムを何度も交換して問題が発生しないようにすることができます。

また、配列が変異していることに注意してください。したがって、ループの繰り返しごとに、配列の最新の状態を操作します。これは、同じインデックスを複数回スワップすると重複を作成していないことを意味します。

Answer 2

それは、Fisher-Yates氏のシャッフルと呼ばれています。ウィキペディアではなく、それについての記事を詳しく説明しています：https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle

Answer 3

はannotated version of the sourceを読む：

Fisher-Yates shuffleの現代版を使用して、コレクションをシャッフルします。

いいえ、randは一意に生成されません。異なる繰り返しで同じ番号にすることができます。しかし、アルゴリズムの設計によって、常にシャッフルされていない要素（範囲[0, i]）を指しています。

Answer 4

これは、ランダム値を処理する悪い実装の良い例です。

Math.roundでは、実際には分散していない結果が得られます。これは、範囲全体の開始と終了を意味し、値の半分しか得られません。

var rand = Math.round(Math.random() * i); 
//    ^^^^^ 

var _ = {}, 
 
    i, 
 
    array = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j'], 
 
    count = { }; 
 

 
_.shuffle = function (array) { 
 
    var newArr = array.slice(); 
 
    for (var i = array.length - 1; i > 0; i--) { 
 
     var rand = Math.round(Math.random() * i); 
 
     var temp = newArr[rand]; 
 
     newArr[rand] = newArr[i]; 
 
     newArr[i] = temp; 
 
    } 
 
    return newArr; 
 
}; 
 

 
array.forEach(function (a) { 
 
    count[a] = count[a] || []; 
 
}); 
 
for (i = 0; i < 100000; i++) { 
 
    _.shuffle(array).forEach(function (a, i) { 
 
     count[a][i] = (count[a][i] || 0) + 1; 
 
    }); 
 
} 
 
console.log(count);

.as-console-wrapper { max-height: 100% !important; top: 0; }

例

var rand = Math.floor(Math.random() * (i + 1)); 
//    ^^^^^     ^^^ 

var _ = {}, 
 
    i, 
 
    array = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j'], 
 
    count = { }; 
 

 
_.shuffle = function (array) { 
 
    var newArr = array.slice(); 
 
    for (var i = array.length - 1; i > 0; i--) { 
 
     var rand = Math.floor(Math.random() * (i + 1)); 
 
     var temp = newArr[rand]; 
 
     newArr[rand] = newArr[i]; 
 
     newArr[i] = temp; 
 
    } 
 
    return newArr; 
 
}; 
 

 
array.forEach(function (a) { 
 
    count[a] = count[a] || []; 
 
}); 
 
for (i = 0; i < 100000; i++) { 
 
    _.shuffle(array).forEach(function (a, i) { 
 
     count[a][i] = (count[a][i] || 0) + 1; 
 
    }); 
 
} 
 
console.log(count);

.as-console-wrapper { max-height: 100% !important; top: 0; }