使用Python random.shuffle打乱列表的最大长度？

Question

我有一个列表，我用Python自带的洗牌函数（random.shuffle）来打乱它。

不过，Python的参考资料上提到：

请注意，对于即使是比较小的 len(x)，x的所有排列组合的总数都比大多数随机数生成器的周期要大；这意味着对于一个长序列，大多数排列组合是无法生成的。

现在，我想知道这个“比较小的len(x)”到底指的是什么。是100，1000，还是10000呢……

Answer 1

他们的意思是，对于n个物体的排列组合（记作n!），数量增长得非常快。

简单来说，n! = n x (n-1) x ... x 1；比如说，5! = 5 x 4 x 3 x 2 x 1 = 120，这意味着有120种不同的方式来打乱一个包含5个项目的列表。

在同一份Python文档中，他们提到2^19937-1作为周期，这个数字大约是4点多乘以10的6001次方。根据维基百科关于阶乘的页面，我猜2000!应该也差不多是这个数量级。（抱歉，我没有找到确切的数字。）

所以基本上，可能的排列组合数量太多了，以至于你几乎不需要担心那些不会出现的情况。

但是如果这真的是个问题（比如有客户要求保证随机性？），你也可以把这个任务交给一些第三方来处理；比如可以看看http://www.random.org/。

Answer 2

我最开始是在Python的源代码里写的那个评论，所以我可以来解释一下 ;-)

当这个评论被添加的时候，Python使用的Wichmann-Hill随机数生成器的周期非常短，甚至连一副牌的所有排列都无法生成。

现在这个周期大得多，2080是目前的上限。文档可以更详细地说明这一点，但那样会变得非常繁琐。

这里有一个非常简单的解释：一个周期为P的伪随机数生成器（PRNG）有P种可能的初始状态。初始状态完全决定了生成的排列。因此，周期为P的伪随机数生成器最多只能生成P种不同的排列（这只是一个绝对的上限，可能达不到）。这就是为什么在这里比较N!和P是正确的计算方式。实际上：

>>> math.factorial(2080) > 2**19937 - 1
False
>>> math.factorial(2081) > 2**19937 - 1
True

Answer 3

总结一下：当列表里的元素超过2080个时，它会“出问题”，但别太担心 :)

完整回答：

首先，要明白“打乱”一个列表可以看作是生成列表中所有元素的排列组合，然后随机选择其中一个。

接下来，你要记住，所有的计算机随机数生成器其实都是“伪”随机的。也就是说，它们并不是真正随机的，而是依赖一系列因素来生成一个难以预测的数字。这些因素通常包括之前生成的数字。因此，实际上如果你连续使用一个随机生成器多次，你最终会开始得到相同的数字序列（这就是文档中提到的“周期”）。

最后，Lib/random.py（随机模块）的文档说明“随机数生成器的周期是 2**19937-1。”

所以，考虑到这些，如果你的列表有 2**19937 或更多的排列组合，其中一些在打乱列表时是永远无法得到的。你会（从概念上讲）生成列表的所有排列，然后生成一个随机数x，选择第x个排列。下次，你再生成一个随机数y，选择第y个排列，依此类推。但由于排列的数量超过了你能生成的随机数（因为最多在生成 2**19937-1 个数字后，你会开始得到相同的数字），你会开始再次选择相同的排列。

所以，你看，这并不完全是列表有多长的问题（虽然这也算在内）。而且， 2**19937-1 是个非常大的数字。不过，还是要根据你的打乱需求考虑这些。在一个简单的例子中（快速计算一下），对于一个没有重复元素的列表，2081个元素会产生 2081! 种排列，这个数量超过了 2**19937。