PHP shuffle函數使用的算法

Question

什麼是php shuffle函數使用的算法，或者我可以在哪裏獲得它的代碼。我必須用C語言來實現它。我已經在C中實現了fisher yates算法，但是php洗牌功能顯示的結果並不好。

Answer 1

什麼構成「不好的結果」？

Fisher-Yates shuffle將以相同的概率產生所有排列，但只有當您正確生成隨機數。這裏需要注意三個問題。首先，你需要一個好的僞隨機數發生器。 C標準庫rand通常是而不是一個很好的PRNG（儘管它取決於你的C庫實現）。如果您使用的是POSIX平臺，請考慮使用lrand48。您的系統可能有其他RNG。如果您的平臺上沒有任何東西，那麼G.Magaglias KISS生成器 - 代碼非常少，您可以找到代碼here。其次，如果您仍然決定使用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; 
}