對一個列表（一維數(shù)組）的完全性洗牌（shuffle）操作，是要讓其元素每種排列模式等概率出現(xiàn)。

列表元素個數(shù)為n，那么其全排列的數(shù)目就是n的階乘“n!”。

偽隨機數(shù)是有周期的，設(shè)周期為m。那基于偽隨機數(shù)映射的元素排列模式也只會有m種。

當(dāng)列表元素很多，n! 會是個天文數(shù)字，大于偽隨機數(shù)周期，那樣永遠有一部分排列模式無法出現(xiàn)。

python標準庫函數(shù)random.shuffle(x)就說明了——“請注意，即使對于小的len(x)，x的排列總數(shù)也可以快速增長，大于大多數(shù)隨機數(shù)生成器的周期。 這意味著長序列的大多數(shù)排列永遠不會產(chǎn)生。 例如，長度為2080的序列是可以在 Mersenne Twister 隨機數(shù)生成器的周期內(nèi)擬合的最大序列。”

要對大于偽隨機數(shù)周期的大列表完全性shuffle，怎么辦呢

我采用的辦法是多輪洗牌，讓基本周期的乘積大于列表元素全排列數(shù)目“n!”，就保證了完全性shuffle的完成。

這里有一個啟發(fā)式的方法：如果需要生成具有n中可能性的隨機數(shù)，那么就需要一個循環(huán)周期長度為n^2的 PRNG（相關(guān)細節(jié)請參考 Pierre L'Ecuyer 的random number generation）。

我寫了這個算法的實現(xiàn)python包，源碼放在GitHub上，complete_shuffle

已經(jīng)發(fā)布到了PyPI上，可以很方便的安裝分發(fā)：

pip install complete-shuffle

此包還包括了Sattolo算法實現(xiàn)的對列表隨機循環(huán)排列。算法介紹見Sattolo算法

和

等概率生成列表的“全錯位排列”函數(shù)，功能實現(xiàn)了可以用于含重復(fù)元素的列表。我使用的是優(yōu)化的接受-拒絕采樣算法，時間復(fù)雜度為O(n)。生成均勻分布“全錯位排列”還有一種優(yōu)化算法，見Generating Random Derangements。此算法時間復(fù)雜度也是O(n)，但聲稱其時間復(fù)雜度的常數(shù)項較低。我看意義不大。

順便說python 3.9版已聲明 random.shuffle() 的 random 形參將被棄用

我寫這個包中函數(shù)就有等同于 random.shuffle() 的 random 的形參?？梢蕴娲鷺藴蕩靣andom.shuffle()函數(shù)了