5

来自 random.shuffle 的Python 文档，它采用一个列表并随机化其元素的顺序：

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

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

4

2 回答 2

5

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

@TryPyPy 链接到的上一个问题也关注 Python，但接受的答案很好地解释了为什么它总是会发生。套用一下，你可以想象一个幼稚的洗牌算法以这种方式工作：

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

如果p长于xPRNG 可以产生的所有可能的 s 的列表，则某些排列是不可达的。

由于花哨的 shuffle 算法的核心是一种这样做的方法，而无需在丢弃除其中一个之外的所有排列之前生成所有可能的排列，因此解决此问题的唯一方法是拥有真正随机性的来源。

于 2012-05-19T04:04:11.900 回答
2

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

这样做的缺点是您的程序可能不得不暂停任意长的时间，而您的操作系统会收集更多的熵供您使用。

于 2012-05-19T03:59:30.963 回答