_.shuffle 这个实现背后的逻辑是什么？

Question

任何人都可以指导我了解此实施变体的工作原理吗？

对于我们如何确保由 var rand 生成的随机数（也就是我们试图访问的索引）是唯一的，我有点困惑，以便确保我们正在洗牌给定的数组。

例如。给定 [1,2,3,4] 我们 return [3,4,2,1] 而不是 [3,3,4,4] 因为生成的随机数恰好重复了 2 和 3 的索引？

  _.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

这叫做 Fisher-Yates 随机播放。维基百科有一篇关于它的详细文章：https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle

Answer 2

阅读 annotated version of the source:

Shuffle a collection, using the modern version of the Fisher-Yates shuffle.

不，rand 不是唯一生成的，它可以在不同的迭代中是相同的数字。但是根据算法的设计，它总是指向 non-shuffled 元素（在 [0, i] 范围内）。

Answer 3

ran 不需要是唯一的。

对于 for 循环的每次迭代，改组算法将交换数组中的两个项目。

因此，如果 ran 不是唯一的，那也没关系，因为我们可以 re-swap 两项乘以而不会引起问题。

另请注意，数组已发生变异。因此，对于循环的每次迭代，我们都对数组的最新状态进行操作。这意味着如果我们多次交换相同的索引，我们不会创建重复项。

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; }

_.shuffle 这个实现背后的逻辑是什么？

What is the logic behind this implementation of _.shuffle?

javascript

underscore.js