Fisher-Yates混洗算法在javascript，现代和内-外版本

Question

我在javascript中实现了两个不同版本的费舍-耶茨洗牌，我想知道我是否犯了任何错误。

我在创造一副扑克牌。我对这些洗牌算法很感兴趣。

传递给下面的rng参数的对象是约翰·巴格的“阿利亚”的包装器，它是一个可播种的PRNG，它应该产生比内置Math.random更好的随机数样本。它的API与Math.random的API相同。

我主要想知道我是否犯了任何错误或误解了我所引用的例子。

/** shuffle

    Shuffle an array. 

    @see http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#The_modern_algorithm

    @param {Array} array
    @param {Function} random Optional RNG. Defaults to Math.random.
    @return {Array} The original array, shuffled.
*/
function shuffle (array, random) {
  var i = array.length, j, swap;
  while (--i) {
    j = (random ? random() : Math.random()) * (i + 1) | 0;
    swap = array[i];
    array[i] = array[j];
    array[j] = swap;
  }
  return array;
}

/** pushRand

    Insert a value into an array at a random index. The element 
    previously at that index will be pushed back onto the end. 

    @see http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#The_.22inside-out.22_algorithm

    @param {Array} object to shuffle.
    @param {Mixed} value to insert.
    @param {Function} optional RNG. Defaults to Math.random.
    @return {Number} The new length of the array.

*/
function pushRand (array, value, random) {
  var j = (random ? random() : Math.random()) * array.length | 0;
  array.push(array[j]);
  array[j] = value;
  return array.length;
}

这是洗牌的演示。重新加载页面可以进行内退洗牌，而点击正面向下的卡片可以完成现代洗牌。

编辑:我在“现代”版本中发现了一个fencepost错误，并在这里修复了它，但它仍然在演示中。还不确定“内-出”版本。

编辑:我不再懒惰了，把这些东西都考虑了出来，所以现在应该更容易看了。新的演示。

编辑:内-外程序也有fencepost错误。应该是这样的，我想：

function pushRand (array, value, random) {
  var j = (random ? random() : Math.random()) * (array.length + 1) | 0;
  array.push(array[j]);
  array[j] = value;
  return array.length;
}

谢谢保罗！

编辑:考虑到Adam的优化建议，新代码如下所示：

/** shuffle

    Shuffle an array. 

    @see http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#The_.22inside-out.22_algorithm

    @param {Array} array Array to shuffle.
    @param {Object} rng Optional RNG. Defaults to Math.
    @return {Array} The original array, shuffled.
*/
function shuffle (array, rng) {
  var i = array.length, j, swap;
  if (!rng) rng = Math;
  while (--i) {
    j = rng.random() * (i + 1) | 0;
    swap = array[i];
    array[i] = array[j];
    array[j] = swap;
  }
  return array;
}

/** pushRand

    Insert a value into an array at a random index. The element 
    previously at that index will be pushed back onto the end. 

    @see http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#The_modern_algorithm

    @param {Array} array Array to insert into.
    @param {Mixed} value Value to insert.
    @param {Object} rng Optional RNG. Defaults to Math.
    @return {Number} The new length of the array.

*/
function pushRand (array, value, rng) {
  var j = (rng || Math).random() * (array.length + 1) | 0;
  array.push(array[j]);
  array[j] = value;
  return array.length;
}

下面是更新的可编辑演示 (底部的相关代码)。

Answer 1

除非您修改内到外代码以通过(index+1)进行缩放

       randomIndex = rand()*(index+1)|0;

你不会涵盖所有的可能性。对于index == 0，您总是生成0 --这是正确的，但只是偶然的。

对于index == 1，您也总是生成0 --而不是0到1之间的50/50分隔。

甲板上的第二张牌错过了成为card[1]的唯一机会。

从那时起，对于每一张卡，同样的问题还会继续，如果您需要+1，randomIndex < index，则不需要randomIndex <= index。

对于最后一张放在甲板上的牌，问题可能会更清楚。对于52张牌，index == 51，所以randomIndex最多可以是50张。因此，任何先前的卡都有可能在卡51结束，但不是最后一张卡。它不能得到接近卡50。

值得欣慰的是，这一变化使得最初洗牌的数学看起来更像重新洗牌。

Answer 2

请注意，您可以优化while循环中的第一行：

 function shuffle (array, random) {
    var i = array.length, j, swap;
    while (--i) {
      j = (random ? random() : Math.random()) * (i + 1) | 0;

对随机的布尔值的检查每次都会发生(根据编译器的不同，我很好地考虑了围绕它的一些优化)。它可能会像这样跑得更快一点：

 function shuffle (array, random) {
    var i = array.length, j, swap;
    random = random || Math.random;
    while (--i) {
      j = random() * (i + 1) | 0;

编辑:有错误的random |= (执行二进制或)-替换为random = random ||