如何随机洗牌具有比PRNG时期更多排列的列表？

Question

我有一个包含大约3900个元素的列表,我需要随机置换以生成统计分布.我环顾四周,用Python random.shuffle找到了这个Maximal Length of List,它解释了Python中PRNG的周期2**19937-1,这导致了一个列表的最大长度,2080然后才能生成所有可能的排列.我只生成300-1000个列表的排列,因此我不太可能产生重复的排列,但是,由于这产生了统计分布,我希望将所有可能的排列作为潜在样本.

Answer 1

我同意@user2357112的观点，即这不太可能是一个真正的问题——但看起来你应该能够使用该标准random所有排列至少都是可能的方式使用标准模块。

你可以采取分而治之的方法。使用初始种子将列表分为 2 个列表，每个列表大约 2000 个。此类分区的数量大致C(4000,2000)为1.66 x 10^1202。这小于周期，这表明至少有可能生成所有此类分区random.sample()。然后 - 重新播种随机数生成器并排列前半部分。然后——第二次重新播种并排列下半场。也许在重新播种之前稍微延迟一下，这样就不会遇到涉及系统时钟分辨率的问题。您还可以尝试将初始列表随机划分为大量较小的列表。

从数学上讲，很容易看出，如果您将列表随机划分为子列表，以便每个分区的可能性相同，然后以所有子列表排列的可能性相同的方式排列每个子列表，并将这些子列表排列粘合在一起以获得整个列表排列，则所有整个列表排列的可能性相同。

这是一个实现：

import random, time

def permuted(items, pieces = 2):
    sublists = [[] for i in range(pieces)]
    for x in items:
        sublists[random.randint(0,pieces-1)].append(x)
    permutedList = []
    for i in range(pieces):
        time.sleep(0.01)
        random.seed()
        random.shuffle(sublists[i])
        permutedList.extend(sublists[i])
    return permutedList

我不确定time.sleep(0.01)是否真的需要。我担心的是，如果重新播种在一毫秒内发生，那么在某些系统上可能会使用相同的种子。

最后一点，仅仅因为上述函数（具有适当的选择pieces）不能通过简单的计数参数（将排列数与初始状态数进行比较）来证明错过某些排列，这并不在它本身就证明了所有排列实际上都是可能的。这需要对随机数生成器、为其提供种子的哈希函数以及洗牌算法进行更详细的分析。