使用Python random.shuffle随机播放的列表的最大长度？

Question

我有一个列表,我用随机的shuffle函数(random.shuffle)

但是,Python参考说明:

注意,即使相当小len(x),x的排列总数也大于大多数随机数生成器的周期; 这意味着永远不会产生长序列的大多数排列.

现在,我想知道这个"相当小的len(x)"意味着什么.100,1000,10000,......

Answer 1

TL; DR:它在超过2080个元素的列表上"中断",但不要太担心:)

完整答案:

首先,注意"清单"列表可以(概念上)理解为生成列表元素的所有可能排列,并随机选择这些排列中的一个.

然后,您必须记住所有自包含的计算机化随机数生成器实际上是"伪"随机的.也就是说,它们实际上并不是随机的,而是依赖于一系列因素来尝试生成一个难以在高级或有目的地再现中猜到的数字.这些因素通常是先前生成的数字.所以,实际上,如果你连续使用一个随机发生器一定次数,你最终会重新开始获得相同的序列(这是文档所指的"时期").

最后,Lib/random.py(随机模块)上的docstring表示"[随机数生成器]的周期是2**19937-1."

因此,考虑到所有这些,如果您的列表具有2**19937或多个排列,则其中一些将永远不会通过混洗列表获得.您(再次,在概念上)生成列表的所有排列,然后生成随机数x,并选择第x个排列.下一次,您生成另一个随机数y,并选择第y个排列.等等.但是,因为有更多的排列而不是随机数(因为,最多2**19937-1生成数字之后,你会再次开始获得相同的数字),你将再次开始选择相同的排列.

所以,你看,这并不是你的清单有多长(尽管这确实进入了等式).而且,这2**19937-1是一个相当长的数字.但是,仍然,根据你的洗牌需求,你应该记住所有这些.在一个简单的情况下(并通过快速计算),对于没有重复元素的列表,2081个元素将产生2081!排列,这超过了2**19937.

Answer 2

我最初在Python源代码中写了那条评论,所以也许我可以澄清一下;-)

当评论被引入时,Python的Wichmann-Hill生成器的周期要短得多,我们甚至无法生成一副卡片的所有排列.

这个时期现在天文数字大,2080对于当前上限是正确的.可以加强文档以更多地说明这一点 - 但它们会变得非常繁琐.

有一个非常简单的解释:周期P的PRNG具有P个可能的起始状态.起始状态完全决定了产生的排列.因此,周期P的PRNG不能产生超过P个不同的排列(并且这是绝对上限 - 它可能无法实现).这就是比较N的原因!在这里,P是正确的计算.确实:

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