PHP shuffle函数使用的算法(The algorithm used by PHP shuffle function)

PHP shuffle函数使用的算法(The algorithm used by PHP shuffle function)

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

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.

最满意答案

究竟什么构成“不好结果”？

Fisher-Yates shuffle将以相同的概率产生所有排列， 但前提是您正确生成随机数 。 这里有三个问题需要注意。 首先，您需要一个好的伪随机数生成器。 C标准库rand通常不是一个好的PRNG（虽然它取决于你的C库实现）。 如果您使用的是POSIX平台，请考虑使用lrand48 。 您的系统可能有其他RNG。 如果你的平台上没有任何东西，那么非常小的代码中的一个非常好的RNG就是G. Marsaglias KISS生成器 - 你可以在这里找到代码。 其次，如果您仍然决定使用rand ，请注意它将生成介于0和RAND_MAX之间的随机数。 对于大量实现， RAND_MAX仅为32767，因此如果count大于32768，通常的rand() % 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; }

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