Python的random.shuffle限制

Question

5

以下是Python文档关于random.shuffle的翻译，该函数接受一个列表并随机排列元素：

请注意，即使对于相当小的len(x)，x的全排列总数也大于大多数伪随机数生成器的周期；这意味着，长序列的大多数排列可能永远无法生成。

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

- Colin

我猜你的意思是“可行的”，而不是“可能的”。 - Joel Cornett

我原本的意思是可行的，但现在我很好奇如果不可行，但确实可能，我们所谈论的是何种疯狂？ - Colin

4

请参阅 https://dev59.com/e3A75IYBdhLWcg3w3NHf 和 http://mail.python.org/pipermail/python-dev/2006-June/065815.html（查看线程，这是一个真正的问题，尽管不太严重）。 - TryPyPy

1

@TryPyPy，那个Python-dev的帖子以Tim Peters声称已经删除了该注释并拒绝将其放回而结束 - 但是根据OP的链接，它仍然存在，并且也在当前开发版本的文档中。这个故事还有后续吗？ - lvc

1

啊，找到了：http://mail.python.org/pipermail/python-ideas/2009-March/003671.html - lvc

2个回答

2

是的，这是可能的。您可以编写一个排列生成器，使用random.SystemRandom来进行所有决策。

但是，缺点是当您的操作系统为您收集更多熵供您使用时，您的程序可能不得不停止任意长的时间。

- btilly

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- lvc · Accepted Answer

请看 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的列表要长，则有些排列是无法到达的。

由于花式洗牌算法本质上是一种在丢弃所有排列之前完成此操作的方法，因此唯一避免这种问题的方法是拥有真正随机的来源。