是否有一种算法可以找到2个列表的唯一组合？5个清单？

一尘不染

是否有一种算法可以找到2个列表的唯一组合？5个清单？

algorithm

我有 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, ... ]

阅读 187

2020-07-28

共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)

编辑：正如豆形软糖指出的那样，原始问题要求唯一的集合。上面的代码不会产生独特套如果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)))]

2020-07-28