Python的random.shuffle限制

Question

来自random.shuffle 的Python文档,它接受一个列表并随机化它的元素的顺序:

注意,对于相当小的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]

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

由于奇特的洗牌算法的核心是一种实现此目的的方法，而无需在丢弃除其中一个之外的所有排列之前生成所有可能的排列，因此解决此问题的唯一方法是拥有真正的随机性来源。