如何生成数组中元素的所有组合？

Question

我有一个列表，这个列表里面有x个子列表，每个子列表里有y个元素。我想把每个元素和其他所有元素配对一次，注意配对是双向的，也就是说(a,b)和(b,a)算是同一对。

补充说明：之前有人觉得我的描述太模糊了，所以我来详细说一下背景。我写了一个函数，它可以生成随机的方程式，然后用一些遗传算法的技巧对这些方程进行变异和交叉，最后根据适应度来选择。经过几轮迭代后，它会返回一个包含12个对象的列表，这些对象是根据它们的“方程”属性的适应度进行排序的。

我使用“parallel python”模块来运行这个函数8次，结果返回了一个包含8个子列表的列表，每个子列表里有12个对象（每个对象都有一个方程属性）。在每个子列表里，这12个对象已经相互交叉过了。现在，我想把一个列表中的每个对象和其他所有列表中的对象进行交叉，但不想和它自己列表中已经交叉过的对象再交叉。（呼！）

Answer 1

首先，请不要把这个称为“数组”。你使用的是一个列表的列表。在Python中，数组是另一种数据结构，是通过array模块提供的。

另外，你的应用听起来很像是在处理矩阵。如果你真的在做矩阵操作，建议你去了解一下Numpy这个包。

乍一看，你的问题听起来像是可以用zip()函数或者itertools.izip()来解决的。你一定要看看itertools模块的文档，因为里面有很多列表操作的方法，而且它们的运行速度比你自己在Python中写的要快。

Answer 2

你没有完全说明你需要什么。听起来 itertools 这个库应该能满足你的需求。也许你想要的是对你大列表中的列表进行 itertools.product 之后，再用 itertools.combinations 来组合。

@fortran：你不能有一组集合。你可以有一组不可变集合（frozensets），但这可能不符合你对重复项的实际需求。

Answer 3

itertools.product 是个好帮手。

关于去掉重复的部分，可以试试用一组集合。

现在你想要的内容变得更清楚了：

import itertools

def recombinate(families):
    "families is the list of 8 elements, each one with 12 individuals"
    for fi, fj in itertools.combinations(families, 2):
        for pair in itertools.product(fi, fj):
            yield pair

基本上，就是从那些并行生成的家庭中，取出所有的2个组合，然后对于每一对家庭，生成所有元素的组合。