有没有算法可以找到两个列表的唯一组合？五个列表呢？

Question

我有N个列表，想要找出它们的独特组合。我在白板上写下了这些，感觉其中有规律，只是还没找到。虽然我觉得可以用一种暴力破解的方法来解决这个问题，这也是我会考虑的方向。可是有没有其他的办法呢？换一种数据结构，比如二叉树，会不会让这个工作变得更合适呢？

给定：

#    1  2
a = [1, 2]
b = [a, b]

结果将是：

c = [1a, 1b, 2a, 2b] # (4 unique combinations)

给定：

v = [1, a]
w = [1, b]
x = [1, c]
y = [1, d]
z = [1, e]

结果将是：

r = [11111, 1bcde, 11cde, 111de, 1111e, a1111, ab111, abc11, abcd1, abcde, 1b1d1, 1bc1e, 11c11, 11c1e, ... ] 

Answer 1

我觉得这个问题并不是在问输入的所有子集，而是在问输入集合的笛卡尔积的一部分。我想如果我说错了，应该会有人来纠正我。

至于算法，既然你现在知道自己在找什么了，谷歌会是你的好帮手。

在你的第二个例子中，你把像1b1de这样的条目排除了结果集。这是故意的吗？如果是故意的，那输出是根据什么规则来构建的呢？

Answer 2

我觉得有必要再补充一个回答，来回应这个问题：

我在白板上写下了这些，感觉它们之间有规律，只是我还没找到。

其实是有规律的。

假设你有两个列表需要合并。你可以通过画一个网格来找出所有的组合。

       black        blue
     +------------+------------+
coat | black coat | blue coat  |
     +------------+------------+
hat  | black hat  | blue hat   |
     +------------+------------+

如你所见，这里有2*2的组合。如果有30种颜色和14种衣服，那你就会有30 * 14 = 420种组合。

随着你添加更多的列表，这个规律会继续。你不再是一个二维的矩形，而是变成了一个三维的盒子，最终会形成一个n维的超矩形。不管怎样，所有组合的总数总是所有列表长度的乘积。

如果你知道有多少个列表，使用嵌套循环是一种自然的方法来生成所有组合。

for color in colors:
    for kind in kinds:
        print color, kind  # "black coat", "black hat", etc.

如果这些列表一开始就是按字典顺序排列的，并且没有重复项，那么输出的结果也会是按字典顺序的。

Answer 3

也许你在找的是 itertools.product：

#!/usr/bin/env python
import itertools
a=[1,2]
b=['a','b']
c=[str(s)+str(t) for s,t in itertools.product(a,b)]
print(c)
['1a', '1b', '2a', '2b']

v=[1,'a']
w=[1,'b']
x=[1,'c']
y=[1,'d']
z=[1,'e']

r=[''.join([str(elt) for elt in p]) for p in itertools.product(v,w,x,y,z)]
print(r)
# ['11111', '1111e', '111d1', '111de', '11c11', '11c1e', '11cd1', '11cde', '1b111', '1b11e', '1b1d1', '1b1de', '1bc11', '1bc1e', '1bcd1', '1bcde', 'a1111', 'a111e', 'a11d1', 'a11de', 'a1c11', 'a1c1e', 'a1cd1', 'a1cde', 'ab111', 'ab11e', 'ab1d1', 'ab1de', 'abc11', 'abc1e', 'abcd1', 'abcde']

注意，product 会产生 2 的 5 次方个元素。这是你想要的吗？

itertools.product 从 Python 2.6 开始就有了。如果你用的是更早的版本，可以使用这个：

def product(*args, **kwds):
        '''
        Source: http://docs.python.org/library/itertools.html#itertools.product
        '''
        # product('ABCD', 'xy') --> Ax Ay Bx By Cx Cy Dx Dy
        # product(range(2), repeat=3) --> 000 001 010 011 100 101 110 111
        pools = map(tuple, args) * kwds.get('repeat', 1)
        result = [[]]
        for pool in pools:
            result = [x+[y] for x in result for y in pool]
        for prod in result:
            yield tuple(prod)

补充：正如 jellybean 指出的，最初的问题是要找唯一的集合。如果 a、b、v、w、x、y 或 z 中有重复的元素，上面的代码就不会产生唯一的集合。如果这是个问题，你可以在传给 itertools.product 之前，把每个列表转换成集合：

r=[''.join([str(elt) for elt in p]) for p in itertools.product(*(set(elt) for elt in (v,w,x,y,z)))]