费舍尔·耶茨能否打乱所有扑克牌排列？

Question

我正在使用标准的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;
}

Answer 1

一般来说，如果伪随机数生成器 (PRNG) 允许少于 52 个阶乘不同种子，则特定 PRNG在打乱 52 项列表时无法选择某些排列，并且 Fisher-Yates 无法更改那。（一个特定的 PRNG 可以选择的排列集合可以与另一个 PRNG 可以选择的排列集合不同，即使两个 PRNG 都是用相同的种子初始化的。这里没有提到允许与数量相同或更多的种子的 PRNG。的排列或 PRNG可以选择的排列是否具有相同的发生概率，而不是生成完全独立的均匀随机整数的理想过程。）另请参阅此问题。

\n

请注意，尽管Math.random在撰写本文时 V8 使用的算法允许大约 2^128 个种子中的任何一个，但 ECMAScript 规范并未强制要求使用特定的随机数算法Math.random，该规范仅声明该方法使用“依赖于实现的算法或策略”来生成随机数（参见 ECMAScript 第 20.2.2.27 节）。

\n\n

PRNG 的周期可以通过 Bays-Durham shuffle 来延长，这有效地增加了 PRNG 的状态长度（参见 Severin Pappadeux 的答案）。但是，如果您仅使用 PRNG 的输出来初始化 Bays-Durham 表条目（而不是使用种子来初始化这些条目），则该特定 PRNG（包括它初始化这些条目的方式）仍然会出现这种情况并根据它生成的伪随机数选择这些表条目）不能选择比可能的种子数量更多的排列来初始化其原始状态，因为只有一种方法来初始化给定种子的 Bays-Durham 条目\xe2\x80\x94 当然，除非 PRNG 实际上对大量列表进行洗牌，数量如此之多，以至于它在不循环的情况下生成的伪随机数比没有 Bays-Durham 洗牌时生成的伪随机数更多。

\n

例如，如果 PRNG 长 128 位，则只有 2^128 个可能的种子，因此只有 2^128 种方法来初始化Bays-Durham shuffle，每个种子一个，除非种子长于 128 位延伸到Bays-Durham 表条目而不仅仅是 PRNG 的原始状态。（这并不意味着 PRNG 可以选择的排列集合始终相同，无论它如何在 Bays-Durham shuffle 中选择表条目。）

\n