python - 查找提供的 Sum 值的组合

Question

我有一系列这样的数字

myvar = [57, 71, 87, 97, 99, 101, 103, 113, 114, 115, 128, 129, 131, 137, 147, 156, 163, 186]

现在我想计算所有这些可能的组合(长度为 1 到 20)，其总和等于给定数字 m。

我试着用下面的代码来解决:

def sum_count(m):    ## Where m is the sum required

    from itertools import combinations

    myseq = []
    for i in range(1,len(myvar)):
        mycomb = list(combinations(mass,i));  # Getting combinations of length i
        mycomb = [list(j) for j in mycomb];
        for j in range(len(mycomb)-1,-1,-1):
            if sum(mycomb[j]) == m:
                myseq.append(mycomb[j])

    return(myseq)

当我输入 m = 270(例如)时，它会给我:

[[114, 156], [57, 99, 114]]

但是从 myvar 中可以明显看出，还有其他组合的总和等于 270。我哪里没理解。

Answer 1

长话短说:

讨论不同的方法，此处列出了最佳方法以便于访问，最初由 thefourtheye 编写:

def subsets_with_sum(lst, target, with_replacement=False):
    x = 0 if with_replacement else 1
    def _a(idx, l, r, t):
        if t == sum(l): r.append(l)
        elif t < sum(l): return
        for u in range(idx, len(lst)):
            _a(u + x, l + [lst[u]], r, t)
        return r
    return _a(0, [], [], target)

注意:上面的方法在下面的原始版本的基础上进行了改进

---

原帖:

好吧 - 通过一些逻辑快速简单地应用您的数据得出结论，您的答案是正确的:

# data
vals = [57, 71, 87, 97, 99, 101, 103, 113, 114, 115, 128, 129, 131, 137, 147, 156, 163, 186]
target = 270

使用 itertools.combinations :

>>> from itertools import combinations
>>> [comb for i in range(1, 20) for comb in combinations(vals, i) if sum(comb) == target]
[(114, 156), (57, 99, 114)]

但是，也许您想使用 combinations_with_replacement它允许从初始列表中多次使用值，而不是只使用一次。

使用 itertools.combinations_with_replacement :

>>> from itertools import combinations_with_replacement
>>> [comb for i in range(1, 20) for comb in combinations_with_replacement(vals, i) if sum(comb) == target]
>>>  # result takes too long ...

---

你可以把它变成一个健壮的函数:

def subsets_with_sum(lst, target, subset_lengths=range(1, 20), method='combinations'):   
    import itertools
    return [comb for i in subset_lengths for comb in
            getattr(itertools, method)(lst, i) if sum(comb) == target]

>>> subsets_with_sum(vals , 270)
[(114, 156), (57, 99, 114)]

---

另一种方法，由thefourtheye提供，它的速度多，并且不需要导入:

def a(lst, target, with_replacement=False):
    def _a(idx, l, r, t, w):
        if t == sum(l): r.append(l)
        elif t < sum(l): return
        for u in range(idx, len(lst)):
            _a(u if w else (u + 1), l + [lst[u]], r, t, w)
        return r
    return _a(0, [], [], target, with_replacement)


>>> s = [57, 71, 87, 97, 99, 101, 103, 113, 114, 115, 128, 129, 131, 137, 147, 156, 163, 186]
>>> a(s, 270)
[[57, 99, 114], [114, 156]]
>>> a(s, 270, True)
[[57, 57, 57, 99], [57, 57, 156], [57, 71, 71, 71], [57, 99, 114], [71, 71, 128], [114, 156]]

---

时间:

def a(lst, target, with_replacement=False):
    def _a(idx, l, r, t, w):
        if t == sum(l): r.append(l)
        elif t < sum(l): return
        for u in range(idx, len(lst)):
            _a(u if w else (u + 1), l + [lst[u]], r, t, w)
        return r
    return _a(0, [], [], target, with_replacement)

def b(lst, target, subset_lengths=range(1, 21), method='combinations'):   
    import itertools
    return [comb for i in subset_lengths for comb in
            getattr(itertools, method)(lst, i) if sum(comb) == target]
    
vals = [57, 71, 87, 97, 99, 101, 103, 113, 114, 115, 128, 129, 131, 137, 147, 156, 163, 186]

from timeit import timeit
print 'no replacement'
print timeit("a(vals, 270)", "from __main__ import vals, a", number=10)
print timeit("b(vals, 270)", "from __main__ import vals, b", number=10)
print 'with replacement'
print timeit("a(vals, 270, True)", "from __main__ import vals, a", number=10)
print timeit("b(vals, 270, method='combinations_with_replacement')", "from __main__ import vals, b", number=10)

定时输出:

no replacement
0.0273933852733
0.683039054001
with replacement
0.0177899423427
... waited a long time ... no results ...

结论:

新方法 (a) 至少快了 20 倍。