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 个不同的阶乘种子，则有一些排列 特定的 PRNG 在打乱 52 项时无法选择列表，Fisher-Yates 无法更改它。（一个特定 PRNG 可以选择的排列集可以不同于另一个 PRNG 可以选择的排列集，即使两个 PRNG 都使用相同的种子初始化。）另请参见 .

请注意，尽管在撰写本文时 V8 使用的 Math.random 算法允许大约 2^128 个种子中的任何一个，但 Math.random 的 ECMAScript 规范并未强制要求任何特定的随机数算法，它仅说明该方法使用 "implementation-dependent algorithm or strategy" 生成随机数（请参阅 ECMAScript sec. 20.2.2.27）。

PRNG 的周期可以通过 Bays-Durham 洗牌来延长，这有效地增加了 PRNG 的状态长度（参见 Severin Pappadeux 的回答）。但是，如果您仅使用 PRNG 的输出初始化 Bays-Durham table 条目（而不是使用种子来初始化这些条目），那个特定的 PRNG （包括它初始化这些条目的方式，并根据它生成的随机数选择那些 table 条目）不能选择比初始化其原始状态的可能种子数更多的排列，因为对于给定的种子，只有一种方法可以初始化 Bays-Durham 条目——当然，除非 PRNG 实际上洗牌的列表数量过多，以至于它在没有循环的情况下生成的随机数比没有 Bays 的随机数多-达勒姆随机播放。

例如，如果 PRNG 的长度为 128 位，则只有 2^128 个可能的种子，因此只有 2^128 种方法可以初始化 Bays-Durham 洗牌，每个种子一个，除非超过 128 位的种子扩展到 Bays-Durham table 条目，而不仅仅是 PRNG 的原始状态。（这并不意味着 PRNG 可以选择的排列组合始终相同，无论它如何选择 Bays-Durham 洗牌中的 table 个条目。）

编辑（8 月 7 日）：澄清。

编辑（2020 年 1 月 7 日）：已编辑。

Answer 2

你是对的。使用 128 位起始状态，最多只能生成 2¹²⁸ 个不同的排列。不管你多久使用一次这个状态（调用Math.random()），PRNG毕竟是确定性的。

Math.random() 的调用次数真正重要的是什么时候

每次调用都会将更多的熵（例如从硬件随机）引入系统，而不是依赖仅初始化一次的内部状态
单个调用结果的熵非常低，您不会在算法的运行上使用整个内部状态

Answer 3

好吧，您肯定需要具有 226 位周期的 RNG 才能涵盖所有排列，@PeterO 在这方面的回答是正确的。但是你可以使用 Bays-Durham shuffle 来延长周期，通过有效地延长 RNG 的状态来支付。 B-D 洗牌 RNG 的周期估计是

P = sqrt(Pi * N! / (2*O))

其中 Pi=3.1415...，N 是 B-D table 大小，O 是原始发电机的周期。如果取整个表达式的 log₂，并使用 Stirling 公式计算阶乘，并假设 P=2²²⁶ 和 O=2¹²⁸，你可以得到 N 的估计值，B-D 算法中 table 的大小。根据粗略计算，N=64 足以获得所有排列。

更新

好的，这是使用 B-D 洗牌扩展的 RNG 的示例实现。首先，我在 Javascript Xorshift128+ 中使用 BigInt 实现，这显然也是 V8 引擎中的默认 RNG。与 C++ 相比，它们在前几十次调用中产生了相同的输出。 128 位种子作为两个 64 位字。 Windows 10 x64，节点 12.7。

const WIDTH = 2n ** 64n;
const MASK  = WIDTH - 1n; // to keep things as 64bit values

class XorShift128Plus { // as described in https://v8.dev/blog/math-random
    _state0 = 0n;
    _state1 = 0n;

    constructor(seed0, seed1) { // 128bit seed as 2 64bit values 
        this._state0 = BigInt(seed0) & MASK;
        this._state1 = BigInt(seed1) & MASK;
        if (this._state0 <= 0n)
            throw new Error('seed 0 non-positive');
        if (this._state1 <= 0n)
            throw new Error('seed 1 non-positive');
    }

    next() {
        let s1 = this._state0;
        let s0 = this._state1;
        this._state0 = s0;
        s1  = ((s1 << 23n) ^ s1 ) & MASK;
        s1 ^= (s1 >> 17n);
        s1 ^= s0;
        s1 ^= (s0 >> 26n);
        this._state1 = s1;
        return (this._state0 + this._state1) & MASK; // modulo WIDTH
    }
}

好的，然后在 XorShift128+ 之上，我实现了 B-D 随机播放，table 大小为 4。为了您的目的，您需要 table 超过 84 个条目，并且是 2 的幂table 更容易处理，所以假设 128 个条目 table（7 位索引）就足够了。无论如何，即使有 4 个条目 table 和 2 位索引，我们也需要知道选择哪些位来形成索引。在原始论文中，B-D 讨论了从 rv 的后面以及从 rv 的前面等挑选它们。这是 B-D shuffle 需要另一个种子值的地方 - 告诉算法从位置 2 和 6 中挑选比特。

class B_D_XSP {
    _xsprng;
    _seedBD = 0n;

    _pos0 = 0n;
    _pos1 = 0n;

    _t; // B-D table, 4 entries
    _Z = 0n;

    constructor(seed0, seed1, seed2) { // note third seed for the B-D shuffle
        this._xsprng = new XorShift128Plus(seed0, seed1);

        this._seedBD = BigInt(seed2) & MASK;
        if (this._seedBD <= 0n)
            throw new Error('B-D seed non-positive');

        this._pos0 = findPosition(this._seedBD);                         // first  non-zero bit position
        this._pos1 = findPosition(this._seedBD & (~(1n << this._pos0))); // second non-zero bit position

        // filling up table and B-D shuffler
        this._t = new Array(this._xsprng.next(), this._xsprng.next(), this._xsprng.next(), this._xsprng.next());
        this._Z = this._xsprng.next();
    }

    index(rv) { // bit at first position plus 2*bit at second position
        let idx = ((rv >> this._pos0) & 1n) + (((rv >> this._pos1) & 1n) << 1n);
        return idx;
    }

    next() {
        let retval = this._Z;
        let j = this.index(this._Z);
        this._Z = this._t[j];
        this._t[j] = this._xsprng.next();
        return retval;
    }
}

使用示例如下。

let rng = new B_D_XSP(1, 2, 4+64); // bits at second and sixth position to make index

console.log(rng._pos0.toString(10));
console.log(rng._pos1.toString(10));

console.log(rng.next());
console.log(rng.next());
console.log(rng.next());

显然，例如 8+128 的第三个种子值会产生与示例中所示不同的排列，您可以尝试一下。

最后一步是通过调用几次（4 次中的 3 次）B-D 洗牌 rng 来制作 226 位随机值，并组合 64 位值（和可能的结转）以制作 226 位随机位，然后将它们转换为牌组洗牌。

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

Can Fisher-Yates shuffle produce all playing card permutations?

javascript

arrays

random

shuffle