大序列的置换测试

Question

我想在一个特别大的数据集上执行一个置换试验，即大约400万个条目。基本上，我需要得到一些随机排列的数据集。通常这样做，是费舍-耶茨洗牌，但它几乎是受PRNG期限的限制.也就是说，一个不超过2080年的序列。

有办法解决随机排列大得多的序列吗？

编辑：这里是一个有趣的相关讨论随机洗牌算法和他们是多少限制了RNG。

Answer 1

我认为问题中有什么不清楚。你是在问：

( 1)我是否可以用一个随机排列产生大量的4000000个元素的随机排列，其中一个大的数目相当于100000000000个随机排列？

或

( 2)我是否可以用PRNG生成每4000000个元素的随机排列？

第一个问题的答案是肯定的，第二个问题的答案是否定的。以Mersenne Twister为例。要生成一个随机排列，您需要生成8.1e+7随机位，即大约2^21个随机32位数。由于Mersenne的周期是2^19997，您可以继续并生成一个巨大的2^19976随机排列，这比您所需要的要多得多。

但是，如果要生成每个可能的随机排列，则需要生成至少2^8100000个随机排列，这超过2^19976。但是没有任何实际的理由来产生每一个可能的排列。

关于评论中关于随机洗牌是否会从所有可能的排列中均匀取样的另一个问题:答案是肯定的。只要你的RNG能产生80000000个连续的均匀随机比特，而Mersenne可以，那么你的采样就会是均匀的。

Answer 2

让我们分析您需要使用的最小位数，以获得真正(伪)一致的随机排列。

将生成的位数设为b。我们希望找到b这样的2^b = n!，所以您至少需要使用log_2(n!)位来生成一个均匀分布的排列，即~= 8.1*10^7

Fisher-yates洗牌(假设32位整数)将需要生成32*n~=32*4,000,000~=1.28*10^8随机比特。

虽然确实存在一些浪费，但它并不像人们想象的那么重要(*需要更多的1.5位)，要得到均匀分布的排列，您将需要更多的2080个随机整数。