PHP shuffle函数使用的算法

Question

php shuffle函数使用的算法是什么,或者我在哪里可以得到它的代码.我必须用C语言实现它.我已经在C中实现了fisher yates算法但是没有像php shuffle函数所示的好结果.

Answer 1

究竟什么构成"不好结果"？

Fisher-Yates shuffle将以相同的概率产生所有排列,但前提是您正确生成随机数.这里有三个问题需要注意.首先,您需要一个好的伪随机数生成器.C标准库rand通常不是一个好的PRNG(虽然它取决于你的C库实现).如果您使用的是POSIX平台,请考虑使用lrand48.您的系统可能有其他RNG.如果您的平台上没有任何东西,那么非常小的代码中的一个非常好的RNG是G. Marsaglias KISS生成器 - 您可以在这里找到代码.其次,如果您仍然决定使用rand,请注意它将生成0到0之间的随机数RAND_MAX.对于许多实现,RAND_MAX只有32767,所以通常rand() % count会有一个非常明显和坏的偏见,如果count大于32768.第三,rand() % count(或lrand48() % count或类似的)实际上也是一个坏主意,因为它也引入了偏见.如果count不是2的幂,则某些数字的概率高于其他数字.而且,在许多发生器中,低阶位比高阶位少得多.您可以尝试通过使用(long long) rand() * count / RAND_MAX或类似的方法来解决这个问题,但实际上您最好使用一个好的RNG.

在0(包括)和k(不包括)之间生成无偏随机数的正确方法是:首先,得到一个适当的PRNG,它给你一个足够大的随机数(比如32个随机位).然后减少到大于2的下一个幂k.最后,如果值大于或等于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;
}