Python 的 random.shuffle 限制

Question

来自Python documentation对于 random.shuffle，它接受一个列表并随机化其元素的顺序:

Note that for even rather small len(x), the total number of permutations of x is larger than the period of most random number generators; this implies that most permutations of a long sequence can never be generated.

这是否适用于任何语言，因为限制似乎取决于随机数生成器？是否可以编写一个函数来生成任意长列表的任何可能排列？

Answer 1

参见 http://mail.python.org/pipermail/python-ideas/2009-March/003670.html .它开始成为问题的确切长度取决于 PRNG，但基本问题将始终适用。

@TryPyPy 链接到的上一个问题也集中在 Python 上，但接受的答案很好地解释了为什么它总是会发生。换句话说，您可以想象一个朴素的洗牌算法以这种方式工作:

1. 生成一个列表，p，包含所有可能的输入排列
2. 从您的 PRNG 中获取一个随机数 x
3. 打乱后的列表是p[x]

如果 p 比 PRNG 可以生成的所有可能 x 的列表长，则某些排列无法到达。

由于花式洗牌算法的核心是一种执行此操作的方法，而不必在丢弃除其中一个之外的所有排列之前生成所有可能的排列，因此解决此问题的唯一方法是拥有真正的随机性来源。