PHP shuffle 函数使用的算法

Question

php shuffle 函数使用的算法是什么或者我在哪里可以获得它的代码。我必须用C语言来实现它。我已经用 C 语言实现了 Fisher yates 算法，但效果不佳，如 php shuffle 函数所示。

Answer 1

“不好的结果”到底是什么？

费舍尔-耶茨洗牌将以相同的概率产生所有排列，但前提是您正确生成随机数。这里需要注意三个问题。首先，您需要一个好的伪随机数生成器。 C 标准库

rand

通常不是一个好的 PRNG（尽管它取决于您的 C 库实现）。如果您使用的是 POSIX 平台，请考虑使用

lrand48

来代替。您的系统可能有其他 RNG。如果您的平台上没有任何东西，G.Marsaglias KISS 生成器是一个非常好的 RNG，代码很少，您可以在here找到代码。其次，如果您仍然决定使用

rand

，请注意它将生成 0 到

RAND_MAX

之间的随机数。对于很多实现来说，

RAND_MAX

只有32767，所以如果

rand() % count

大于32768，通常的

count

将会有一个非常明显和不好的偏差。第三，

rand() % count

（或

lrand48() % count

或类似的东西）是实际上也是一个坏主意，因为它也引入了偏见。如果

count

不是 2 的幂，则某些数字的概率将高于其他数字。此外，在许多生成器中，低位比特的随机性比高位位低得多。您可以尝试使用

(long long) rand() * count / RAND_MAX

或类似的东西来解决这个问题，但实际上您最好使用好的 RNG。

生成 0（含）和

k

（不包括）之间无偏随机数的正确方法是：首先，获得一个合适的 PRNG，它可以为您提供足够大的随机数（例如 32 个随机位）。然后减少到比

k

大的 2 次方。最后，如果该值大于或等于

k

，请重试。这是一种完全公正的方法，并且将给出与 PRNG 所能达到的一样好的结果。代码看起来像这样：

static unsigned int random(unsigned int k)
{
  // You can get rid of this loop using bit tricks, but I keep it for clarity     
  unsigned int n, nextpow2 = 1;
  while (nextpow2 < k) 
    nextpow2 *= 2;

  do {
    n = random32() & (nextpow2 - 1); // random32 is your 32-bit RNG
  } while (n >= k);

  return n;
}

Answer 2

对于其他想要寻找标题中问题答案的人，答案是：

PHP shuffle 函数使用 Fisher-Yates 算法，该函数的源代码可以在 PHP GitHub 存储库的 array.c 文件 中找到（搜索

shuffle()

即可找到）。