javascript - 费舍尔·耶茨能否改组产生所有扑克牌排列？

我正在使用标准的Fisher-Yates算法来随机洗牌数组中的一副纸牌。但是，我不确定这是否会真正产生现实世界中经过洗牌的纸牌的所有可能排列的真实分布。

V8的Math.random仅具有128位内部状态。由于套牌中有52张卡，因此52个阶乘将需要226位内部状态才能生成所有可能的排列。

但是，我不确定在使用Fisher-Yates时是否适用，因为您实际上并没有生成每种可能的值，而只是随机地从52个位置中得到一个位置。

function shuffle(array) {
  var m = array.length, t, i;

  while (m) {
    i = Math.floor(Math.random() * m--);
    t = array[m];
    array[m] = array[i];
    array[i] = t;
  }

  return array;
}

最佳答案

通常，如果伪随机数生成器允许少于52个阶乘的不同种子，则某些PRNG混洗52个项目列表时将无法选择某些排列，而Fisher-Yates不能更改。 (即使两个PRNG都使用相同的种子初始化，一个特定PRNG可以选择的排列集合也可以与另一个PRNG可以选择的排列集合不同。)另请参见this question。

请注意，尽管在撰写本文时，V8使用的Math.random算法可以接受大约2 ^ 128个种子，但是ECMAScript的Math.random规范并未要求使用任何特定的随机数算法，该规范仅声明该方法使用的是“与实现相关的” “算法或策略”以生成随机数(请参阅ECMAScript第20.2.2.27节)。

可以使用Bays-Durham洗牌来延长PRNG的期限，这有效地增加了PRNG的州长(请参阅Severin Pappadeux的回答)。但是，如果仅使用PRNG的输出来初始化Bays-Durham表条目(而不是使用种子来初始化这些条目)，则特定的PRNG(包括其初始化那些条目的方式)仍然会出现这种情况。并根据其生成的随机数选择这些表条目)不能选择比可能的种子数量更多的排列来初始化其原始状态，因为对于给定的种子，只有一种方法来初始化Bays-Durham条目-除非，当然，PRNG实际上会洗改大量的列表，如此之多，以至于在没有循环的情况下生成的随机数比没有在Bays-Durham洗消情况下的随机数要多。

例如，如果PRNG长为128位，则只有2 ^ 128个可能的种子，因此只有2 ^ 128种方法初始化Bays-Durham混洗，每个种子都有一个，除非长于128位的种子扩展到Bays-Durham表条目，而不仅仅是PRNG的原始状态。 (这并不意味着PRNG可以选择的排列的集合总是相同的，无论它如何选择Bays-Durham随机播放中的表条目。)

编辑(8月7日):澄清。

编辑(2020年1月7日):编辑。

关于javascript - 费舍尔·耶茨能否改组产生所有扑克牌排列？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/57332878/