序列中所有值对组合（2元组） - PYTHON 2.7

Question

我现在有点脑袋发懵，谷歌也没能帮我解决这个问题。

我有一串包含两个元素的元组（来自一个Counter对象），我想快速而优雅地让Python输出所有这些元组的可能组合，形成一个线性序列或数组。我想找到Counter对象的结果组合。

为了更清楚地说明，如果我有这样一个序列：

[(500, 2), (250, 1)]  

手动做这个例子，应该得到这些结果：

250, 500, 750, 1000, 1250. 

基本上，我觉得是a*b，然后把结果列表加在一起……我试过这个（其中c是Counter对象）：

res = [[k*(j+1) for j in range(c[k])] for k in c]

结果是：

res = [[250], [500, 1000]]

到目前为止还不错，它在遍历每个元组，并对每个y进行x * y的乘法……但结果列表还没有包含所有组合，第一列表[250]需要加到第二列表的每个元素上。我相信对于任何数量的结果都是这样。

现在我觉得我需要把这个结果列表中的每个列表依次加到其他列表的其他元素上。我这样做是不是错了？我觉得应该有更简单的方法。我觉得应该能用一行代码搞定。

这个解决方案是递归的吗？有没有我不知道的神奇导入或内置方法？我头疼……

Answer 1

在这里提到的 v*f 这种乘法，可以不使用，参考了 @DSM的回答。

>>> from itertools import product
>>> terms = [(500, 2), (250, 1)]
>>> map(sum, product(*[xrange(0, v*a+1, v) for v, a in terms]))
[0, 250, 500, 750, 1000, 1250]

如果你想得到一个没有重复项的排序结果，可以使用下面的方法：

from itertools import groupby, imap
from operator import itemgetter

it = imap(itemgetter(0), groupby(sorted(it)))

不过你用的 sorted(set(it)) 在这种情况下也是可以的。

Answer 2

我不太确定我理解你的意思，但也许你在寻找类似这样的东西：

from itertools import product

def lincombs(s):
    terms, ffs = zip(*s)
    factors = product(*(range(f+1) for f in ffs))
    outs = (sum(v*f for v,f in zip(terms, ff)) for ff in factors if any(ff))
    return outs

这样会得到：

>>> list(lincombs([(500, 2), (250, 1)]))
[250, 500, 750, 1000, 1250]
>>> list(lincombs([(100, 3), (10, 3)]))
[10, 20, 30, 100, 110, 120, 130, 200, 210, 220, 230, 300, 310, 320, 330]