从排列生成器随机选择？

Question

如何从 itertools.permutations(k) 中随机选择所有结果，一次一个（不重复）？或者说，如何构建一个随机排列的生成器？就像 shuffle(permutations(k)) 这样。我正在使用 Python 2.6。

是的，如果 r = list(permutations(k))，那么可以使用 shuffle(r)，但是当 len(k) 超过 10 时，这样的列表会占用太多时间和内存。

谢谢。

Answer 1

你想要的功能，实际上只能通过自己写一个 permutations 的版本来实现。

想想这个情况：

• 我们有一个生成器对象，它里面包含了 permutations 的结果。
• 我们写了一个自己的函数来计算这个生成器的长度。
• 然后我们在列表的开头和结尾之间随机选择一些条目。

因为我们用的是生成器，如果随机函数选到了列表后面的某个条目，那么要到达那里，就必须先经过前面的所有条目。这样做要么是把它们丢掉，这样不好，要么就是把它们存到一个列表里，但你也提到过，当选项很多的时候，这样做会有问题。

你是打算遍历每一个排列，还是只用几个？如果是后者，那随机生成每一个新的排列，然后把你见过的存到一个 set 里会更合理。如果你用的数量不多，每次碰到重复时生成新排列的开销其实也不会太大。

Answer 2

我不知道Python是怎么实现它的洗牌算法的，但下面这个方法的时间复杂度是线性的，所以我不明白为什么长度为10会有这么大的问题（除非我误解了你的问题）：

• 首先准备好一个物品列表；
• 然后依次遍历列表中的每个位置，把这个位置的物品和剩下列表中一个随机位置的物品交换（包括它自己）。

如果想要得到不同的排列，只需再运行一次相同的算法。

Answer 3

这个代码可以得到一个列表的第n个排列。

def perm_given_index(alist, apermindex):
    alist = alist[:]
    for i in range(len(alist)-1):
        apermindex, j = divmod(apermindex, len(alist)-i)
        alist[i], alist[i+j] = alist[i+j], alist[i]
    return alist

其中，apermindex 的值应该在 0 和 factorial(len(alist)) 之间。