我有一个数字列表,例如
numbers = [1, 2, 3, 7, 7, 9, 10]
如您所见,数字可能会在此列表中出现多次。
我需要获得具有给定总和的这些数字的所有组合,例如10
。
组合中的项目可能不会重复,但numbers
中的每个项目都必须被唯一处理,这意味着例如列表中的两个7
表示具有相同值的不同项目。
顺序是不重要的,所以[1, 9]
和[9, 1]
是相同的组合。
组合没有长度限制,[10]
与[1, 2, 7]
一样有效。
如何创建符合上述条件的所有组合的列表?
在这个例子中,它将是[[1,2,7], [1,2,7], [1,9], [3,7], [3,7], [10]]
您可以使用itertools迭代每个可能大小的每个组合,并过滤掉不总和为10的所有内容:
import itertools
numbers = [1, 2, 3, 7, 7, 9, 10]
result = [seq for i in range(len(numbers), 0, -1) for seq in itertools.combinations(numbers, i) if sum(seq) == 10]
print result
结果:
[(1, 2, 7), (1, 2, 7), (1, 9), (3, 7), (3, 7), (10,)]
不幸的是,这类似于O(2 ^ N)复杂度,因此它不适合大于20个元素的输入列表。
solution @kgoodrick offered很棒,但我认为它作为发电机更有用:
def subset_sum(numbers, target, partial=[], partial_sum=0):
if partial_sum == target:
yield partial
if partial_sum >= target:
return
for i, n in enumerate(numbers):
remaining = numbers[i + 1:]
yield from subset_sum(remaining, target, partial + [n], partial_sum + n)
list(subset_sum([1, 2, 3, 7, 7, 9, 10], 10))
收益[[1, 2, 7], [1, 2, 7], [1, 9], [3, 7], [3, 7], [10]]
。
之前已经问过这个问题,请参阅@msalvadores回答here。我更新了在python 3中运行的python代码:
def subset_sum(numbers, target, partial=[]):
s = sum(partial)
# check if the partial sum is equals to target
if s == target:
print("sum(%s)=%s" % (partial, target))
if s >= target:
return # if we reach the number why bother to continue
for i in range(len(numbers)):
n = numbers[i]
remaining = numbers[i + 1:]
subset_sum(remaining, target, partial + [n])
if __name__ == "__main__":
subset_sum([3, 3, 9, 8, 4, 5, 7, 10], 15)
# Outputs:
# sum([3, 8, 4])=15
# sum([3, 5, 7])=15
# sum([8, 7])=15
# sum([5, 10])=15
这有效......
from itertools import combinations
def SumTheList(thelist, target):
arr = []
p = []
if len(thelist) > 0:
for r in range(0,len(thelist)+1):
arr += list(combinations(thelist, r))
for item in arr:
if sum(item) == target:
p.append(item)
return p