PHP shuffle函数使用的算法

Question

What is the algorithm used by php shuffle function or where can i get its code. I have to implement it in C language. I have implemented fisher yates algo in C but not good results as showed by php shuffle function.

Answer 1

What exactly constitutes "not good results"?

The Fisher-Yates shuffle will produce all permutations with equal probability, but only if you generate your random numbers correctly. There's three issues to be aware of here. First, you need a good pseudorandom number generator. The C standard library rand usually is not a good PRNG (though it depends on your C library implementation). If you're on a POSIX platform, consider using lrand48 instead. Your system may have other RNGs. If you don't have anything on your platform, a pretty good RNG in very little code is G. Marsaglias KISS generator - you can find the code here. Second, if you still decide to use rand, be aware that it will generate random numbers between 0 and RAND_MAX. For lots of implementations, RAND_MAX is only 32767, so the usual rand() % count will have a very obvious and bad bias if count is larger than 32768. Third, rand() % count (or lrand48() % count or anything similar) is actually a bad idea too, because it too introduces a bias. If count isn't a power of 2, some numbers will have a higher probability than others. Also, in a lot of generators, the low-order bits are a lot less random than the high-order bits. You can try to work around this by using (long long) rand() * count / RAND_MAX or something similar, but really you're better of using a good RNG instead.

The proper way to generate unbiased random numbers between 0 (inclusive) and k (exclusive) is this: First, get a proper PRNG that gives you a large-enough random number (say 32 random bits). Then reduce to the next power of 2 larger than k. Finally, if the value is greater than or equal to k, try again. This is a completely unbiased method, and will give results that are as good as your PRNG can make them. The code looks something like this:

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;
}