python - 在 O(N) 中不放回地采样 k 个随机排列

Question

我需要高效地对列表进行一些独特的随机排列，而无需替换。我目前的做法:

total_permutations = math.factorial(len(population))
permutation_indices = random.sample(xrange(total_permutations), k)
k_permutations = [get_nth_permutation(population, x) for x in permutation_indices]

哪里get_nth_permutation确实像听起来一样高效(意思是 O(N))。但是，这仅适用于 len(population) <= 20 ，仅仅因为 21!太长了以至于xrange(math.factorial(21))不会工作:

OverflowError: Python int too large to convert to C long

是否有更好的算法可以在 O(N) 中对 k 个唯一排列进行采样而不用放回？

Answer 1

在某种程度上，没有必要使用get_nth_permutation 来获取排列。只需洗牌即可!

>>> import random
>>> l = range(21)
>>> def random_permutations(l, n):
...     while n:
...         random.shuffle(l)
...         yield list(l)
...         n -= 1
... 
>>> list(random_permutations(l, 5))
[[11, 19, 6, 10, 0, 3, 12, 7, 8, 16, 15, 5, 14, 9, 20, 2, 1, 13, 17, 18, 4], 
 [14, 8, 12, 3, 5, 20, 19, 13, 6, 18, 9, 16, 2, 10, 4, 1, 17, 15, 0, 7, 11], 
 [7, 20, 3, 8, 18, 17, 4, 11, 15, 6, 16, 1, 14, 0, 13, 5, 10, 9, 2, 19, 12], 
 [10, 14, 5, 17, 8, 15, 13, 0, 3, 16, 20, 18, 19, 11, 2, 9, 6, 12, 7, 4, 1], 
 [1, 13, 15, 18, 16, 6, 19, 8, 11, 12, 10, 20, 3, 4, 17, 0, 9, 5, 2, 7, 14]]

对于 len(l) > 15 和 n < 100000，此列表中出现重复项的几率是压倒性的，但是如果您需要保证，或者对于较低的值len(l)，如果这是一个问题，只需使用 set 来记录和跳过重复项(尽管正如您在评论中观察到的那样，如果 n 接近 len(l)!，这将停止)。像这样的东西:

def random_permutations(l, n):    
    pset = set()
    while len(pset) < n:
        random.shuffle(l)
        pset.add(tuple(l))
    return pset

然而，随着 len(l) 变得越来越长，random.shuffle 变得越来越不可靠，因为列表的可能排列数增加超过了周期随机数发生器!因此，并非 l 的所有排列都可以通过这种方式生成。到那时，您不仅需要将 get_nth_permutation 映射到一系列随机数，您还需要一个能够生成 0 和 len(l)!分布比较均匀。这可能需要您找到更强大的随机性来源。

但是，一旦有了它，解决方案就很简单 Mark Ransom的答案。

要了解为什么 random.shuffle 对于大型 len(l) 变得不可靠，请考虑以下内容。 random.shuffle 只需要在 0 和 len(l) - 1 之间选择随机数。但它根据其内部状态选择这些数字，并且它只能采用有限(且固定)数量的状态。同样，您可以传递给它的可能种子值的数量是有限的。这意味着它可以生成的唯一数字序列集也是有限的；调用该集合 s。对于len(l)! > len(s)，某些排列永远无法生成，因为与这些排列对应的序列不在 s 中。

这成为问题的确切长度是多少？我不知道。但就其值(value)而言，由 random 实现的梅森扭曲周期为 2**19937-1 . shuffle docs笼统地重申我的观点；另请参阅维基百科对此事的看法here .