Python 查找具有给定总和的数字列表的所有组合
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/34517540/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Find all combinations of a list of numbers with a given sum
提问by Byte Commander
I have a list of numbers, e.g.
我有一个数字列表，例如
numbers = [1, 2, 3, 7, 7, 9, 10]
As you can see, numbers may appear more than once in this list.
如您所见，数字可能会在此列表中多次出现。
I need to get all combinations of these numbers that have a given sum, e.g. 10.
我需要获得具有给定总和的这些数字的所有组合，例如10.
The items in the combinations may not be repeated, but each item in numbershas to be treated uniquely, that means e.g. the two 7in the list represent different items with the same value.
组合中的项目可能不会重复，但numbers必须单独处理每个项目，这意味着例如7列表中的两个项目代表具有相同值的不同项目。
The order is unimportant, so that [1, 9]and [9, 1]are the same combination.
顺序不重要，因此[1, 9]和[9, 1]是相同的组合。
There are no length restrictions for the combinations, [10]is as valid as [1, 2, 7].
组合没有长度限制，[10]与[1, 2, 7].
How can I create a list of all combinations meeting the criteria above?
如何创建满足上述条件的所有组合的列表？
In this example, it would be [[1,2,7], [1,2,7], [1,9], [3,7], [3,7], [10]]
在这个例子中，它将是 [[1,2,7], [1,2,7], [1,9], [3,7], [3,7], [10]]
采纳答案by Kevin
You could use itertools to iterate through every combination of every possible size, and filter out everything that doesn't sum to 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
Result:
结果：
[(1, 2, 7), (1, 2, 7), (1, 9), (3, 7), (3, 7), (10,)]
Unfortunately this is something like O(2^N) complexity, so it isn't suitable for input lists larger than, say, 20 elements.
不幸的是，这有点像 O(2^N) 复杂度，所以它不适合大于 20 个元素的输入列表。
回答by kgoodrick
This question has been asked before, see @msalvadores answer here. I updated the python code given to run in python 3:
这个问题已经被问过，看到@msalvadores回答这里。我更新了在 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
回答by Martin Valgur
The solution @kgoodrick offeredis great but I think it is more useful as a generator:
@kgoodrick 提供的解决方案很棒，但我认为它作为生成器更有用：
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))yields [[1, 2, 7], [1, 2, 7], [1, 9], [3, 7], [3, 7], [10]].
list(subset_sum([1, 2, 3, 7, 7, 9, 10], 10))产量[[1, 2, 7], [1, 2, 7], [1, 9], [3, 7], [3, 7], [10]]。
回答by MarsNebulaSoup
This works...
这工作...
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
回答by max
@qasimalbaqali
@qasimalbaqali
This may not be exactly what the post is looking for, but if you wanted to:
这可能不是该帖子正在寻找的内容，但如果您想：
Find all combinations of a range of numbers [lst], where each lst contains N number of elements, and that sum up to K: use this:
找到一系列数字 [lst] 的所有组合，其中每个 lst 包含 N 个元素，总和为 K：使用：
# Python3 program to find all pairs in a list of integers with given sum
from itertools import combinations
def findPairs(lst, K, N):
return [pair for pair in combinations(lst, N) if sum(pair) == K]
#monthly cost range; unique numbers
lst = list(range(10, 30))
#sum of annual revenue per machine/customer
K = 200
#number of months (12 - 9 = num months free)
N = 9
print('Possible monthly subscription costs that still equate to 0 per year:')
#print(findPairs(lst, K, N))
findPairs(lst,K,N)
Results:
结果：
Possible monthly subscription costs that still equate to 0 per year:
Out[27]:
[(10, 11, 20, 24, 25, 26, 27, 28, 29),
(10, 11, 21, 23, 25, 26, 27, 28, 29),
(10, 11, 22, 23, 24, 26, 27, 28, 29),
The idea/question behind this was "how much can we charge per month if we give x number of months free and still meet revenue targets".
这背后的想法/问题是“如果我们免费提供 x 个月的费用并且仍然满足收入目标，我们每月可以收取多少费用”。
