2

我需要一个列表的许多唯一随机排列而不用替换，有效。我目前的做法：

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]

whereget_nth_permutation完全按照听起来的样子，有效地（意思是 O(N)）。但是，这只适用于len(population) <= 20，因为 21! 太长了，xrange(math.factorial(21))无法正常工作：

OverflowError: Python int too large to convert to C long

是否有更好的算法来采样 k 个唯一排列而不用 O(N) 替换？

4

5 回答 5

6

到一定程度，没有必要使用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 和< 100000的重复项的可能性压倒性地大n，但是如果您需要保证，或者对于较低的评论，如果接近，这将停止）。就像是：len(l)setnlen(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.shufflelarge 变得不可靠len(l)，请考虑以下内容。random.shuffle只需要在0和之间选择随机数len(l) - 1。但它会根据其内部状态选择这些数字，并且它只能采用有限（和固定）数量的状态。同样，您可以传递给它的可能种子值的数量是有限的。这意味着它可以生成的唯一数字序列集也是有限的；调用那个集合s。对于len(l)! > len(s)，永远无法生成某些排列，因为与这些排列相对应的序列不在s.

What are the exact lengths at which this becomes a problem? I'm not sure. But for what it's worth, the period of the mersenne twister, as implemented by random, is 2**19937-1. The shuffle docs reiterate my point in a general way; see also what Wikipedia has to say on the matter here.

于 2012-04-19T17:05:32.470 回答
4

而不是xrange简单地继续生成随机数，直到您拥有所需的数量为止。使用 aset确保它们都是唯一的。

permutation_indices = set()
while len(permutation_indices) < k:
    permutation_indices.add(random.randrange(total_permutations))
于 2012-04-19T16:37:24.367 回答
1

我有一个 nth_permutation 的实现（不确定我从哪里得到它），我为了你的目的而修改了它。我相信这足以满足您的需要

>>> def get_nth_permutation(population):
    total_permutations = math.factorial(len(population))

    while True:
        temp_population = population[:]
        n = random.randint(1,total_permutations)
        size = len(temp_population)
        def generate(s,n,population):
            for x in range(s-1,-1,-1):
                fact = math.factorial(x)
                d = n/fact
                n -= d * fact
                yield temp_population[d]
                temp_population.pop(d)
        next_perm = generate(size,n,population)
        yield [e for e in next_perm]


>>> nth_perm = get_nth_permutation(range(21))
>>> [next(nth_perm) for k in range(1,10)]
于 2012-04-19T16:53:38.290 回答
0

您似乎正在寻找Knuth Shuffle！祝你好运！

于 2012-04-19T16:25:03.800 回答
0

您可以使用itertools.islice而不是xrange()：

CPython 实现细节：xrange() 旨在简单和快速实现可能会施加限制来实现这一点。Python 的 C 实现将所有参数限制为原生 C long（“短”Python 整数），并且还要求元素的数量适合原生 C long。如果需要更大的范围，可以使用 itertools 模块制作替代版本：islice(count(start, step), (stop-start+step-1+2*(step<0))//step)。

于 2012-04-19T16:45:00.373 回答