javascript - Fisher-Yates 洗牌可以产生所有纸牌排列吗？

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

一般来说，如果伪随机数生成器允许少于 52 个不同的阶乘种子，那么在打乱 52 项列表时，特定的 PRNG 无法选择一些排列，而 Fisher-耶茨无法改变这一点。 (一个特定 PRNG 可以选择的排列集可以不同于另一个 PRNG 可以选择的排列集，即使两个 PRNG 都使用相同的种子进行初始化。)另请参见 this question。 .

请注意，尽管在撰写本文时 V8 使用的 Math.random 算法允许大约 2^128 个种子中的任何一个，但是 Math.random，仅声明该方法使用“依赖于实现的算法或策略”来生成随机数(请参阅 ECMAScript sec. 20.2.2.27)。

---

PRNG 的周期可以通过 Bays-Durham 洗牌来延长，这有效地增加了 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 日):已编辑。