从置换生成器中随机挑选？

Question

如何从itertools.permutations(k)中随机抽取所有结果，一个接一个(不重复)？或者这样:如何构建一个随机排列的生成器？就像shuffle(permutations(k))一样。我使用的是Python 2.6。

是的，如果是r = list(permutations(k))，可以使用shuffle(r)，但是当len(k)上升到10以上时，这样的列表将占用太多的时间和内存。

谢谢。

Answer 1

这给出了列表的第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))之间的位置

Answer 2

我不知道python是如何实现其混洗算法的，但以下是线性时间的比例，所以我不明白为什么10的长度是一个大问题(除非我误解了您的问题？)：

• 从项目列表开始；
• 依次遍历列表中的每个索引，将该索引处的项目交换为列表其余部分中随机索引处的项目(包括项目本身)。

对于不同的排列，只需再次运行相同的算法。

Answer 3

如果不编写您自己版本的permutations，就无法完成您所要求的工作。

请考虑以下内容：

• 我们有一个包含permutations.
• We结果的生成器对象已经编写了我们自己的函数来告诉我们生成器的长度。
• 然后我们在列表的开头和结尾之间随机挑选一个条目。

由于我有一个生成器，如果随机函数选择列表末尾附近的条目，则到达该生成器的唯一方法将是遍历所有先前的条目，然后丢弃它们，这是不好的，或者将它们存储在列表中，您已经指出，当您有很多选择时，这是有问题的。

您是要遍历每个排列，还是只使用几个？如果是后者，那么随机生成每个新的排列并将其存储在set中会更有意义。如果您不使用那么多，那么每次发生冲突时必须创建一个新的排列的开销将会非常低。