Python的random.shuffle限制

Question

從Python documentation爲random.shuffle，它接受一個列表，並會隨機的順序，如果它的元素：

注意，即使相當小LEN（X）的 總數x的排列大於大多數隨機數 發生器的週期;這意味着長序列的絕大部分排列可能永遠不會生成 。

這是真的對任何語言，因爲限制似乎取決於隨機數發生器？是否可以編寫一個函數來生成任意長的列表的任何可能的排列？

Answer 1

請參閱http://mail.python.org/pipermail/python-ideas/2009-March/003670.html。它開始出現問題的確切長度取決於PRNG，但基本問題始終適用。

@TryPyPy鏈接到的上一個問題也集中在Python上，但接受的答案很好地解釋了爲什麼它總是會發生。套用，你能想象一個天真的洗牌算法，這種方式工作：

1. 生成一個列表，p輸入的所有可能的排列
2. 得到一個隨機數，x，從您的PRNG
3. 的的，洗牌名單p[x]

如果p比所有可能x s表示該PRNG可以產生的名單更長，一些置換的不可達。

由於花式洗牌算法的核心是這樣做，而不必在丟棄其中的一個之前生成所有可能的排列，唯一的方法是獲得真正的隨機性來源。

Answer 2

是的，這是可能的。您可以編寫一個置換生成器，它使用random.SystemRandom作爲您的所有決定。

這樣做的缺點是，當您的操作系統收集更多的熵供您使用時，您的程序可能不得不停止任意長的時間。