是否有算法来查找2个列表的唯一组合？ 5个列表？

Question

我有否列表我希望找到独特的组合。我写在白板上，似乎都有一个模式，我还没有发现它。我觉得我可以表达一种蛮力的方法，这肯定是我追求的。有其他选择吗？一个不同的数据结构（二叉树？）会使这样的工作更合适吗？

鉴于：

# 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

也许你正在寻找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'] 

注意，产品产量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)))] 

Answer 2

我不认为问题要求输入的权力，我认为它要求输入集的笛卡尔积（的一部分）。我希望有人会纠正我，如果我错了。

而且，至于算法，现在好了，你知道你在找什么，谷歌将成为你的朋友。

在第二个示例中，您从结果集中排除了诸如1b1de之类的条目。这是故意的吗？如果是故意的，输出结构的规则是什么？

Answer 3

您正在寻找笛卡尔产品。在Python中，如果你想元组：

c = [(x, y) for x in a for y in b] 
r = [(vv, ww, xx, yy, zz) 
    for vv in v for ww in w for xx in x for yy in y for zz in z] 

Answer 4

我假设你想要的笛卡尔积 - 通过精确地选择创建的所有可能的列表每个列表中有一个元素。你可以递归地实现它，像这样：

def cartesian_product(l): 
    if l: 
     for b in cartesian_product(l[1:]): 
      for a in l[0]: 
       yield [a] + b 
    else: 
     yield []   

l = [ 
[ 'a', 'b' ], 
[ 'c', 'd', 'e' ], 
[ 'f', 'g' ], 
] 

for x in cartesian_product(l): 
    print x 

更新：〜itertools.product的unutbu的建议是好，但我会在这里反正离开这个。

Answer 5

由于您需要笛卡尔产品，请使用itertools！

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

>>> p = [''.join(str(x) for x in c) for c in itertools.product(v,w,x,y,z)] 
>>> p 
['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', 'ab1d 
1', 'ab1de', 'abc11', 'abc1e', 'abcd1', 'abcde'] 
>>> 

Answer 6

可能会这样做吗？

def getAllCombinations(listOfLists): 
    if len(listOfLists) == 1: 
     return [str(x) for x in listOfLists[0]] 

    result = set() 
    head, tail = listOfLists[0], listOfLists[1:] 

    tailCombs = getAllCombinations(tail) 
    for elem in head: 
     for tc in tailCombs: 
      result.add(str(elem) + tc) 
    return result 

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

>>> print getAllCombinations([v, w, x, y, z]) 
set(['111de', 'abc11', 'a1c1e', 'a111e', '11c11', 'ab11e', '1bc11', 'ab1d1', 'a1cd1', '1b1de', 'a11d1', '11111', '1b111', '11cd1', 'abcd1', '1bcde', 'ab111', '1bc1e', 'abc1e', '111d1', 'a1111', '11c1e', 'a1c11', '11cde', '1b11e', '1bcd1', 'abcde', 'a1cde', '1b1d1', 'a11de', 'ab1de', '1111e']) 

Answer 7

我认为另一个答案是为了，能够对此做出反应：

我写出来我的白板，这一切似乎都一个模式，我只是还没有找到还没完成。

There is a pattern。

假设您只有两个要组合的列表。您可以通过制作网格来找到所有组合。

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

正如你所看到的，有2 * 2个组合。如果有30种颜色和14种服装，你会有30 * 14 = 420种组合。

该模式继续添加更多列表。您将得到一个三维的方框数组，或者最终得到一个三维超矩形，而不是一个二维矩形。无论如何，组合的总数总是所有列表的长度的乘积。

如果您知道您有多少个列表，嵌套循环是进行所有组合的自然方式。

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

如果列表是按字典顺序开头的，并且没有重复项，则输出也将按字典顺序排列。