查找提供的Sum值的组合 [英] Finding Combinations to the provided Sum value
问题描述
我有一系列这样的数字
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）：##其中m是itertools导入组合所需的
的总和
myseq = []
对于范围内的i（1，len（myvar ））：
mycomb = list（组合（mass，i））; ＃获得长度的组合i
mycomb = [list（j）for mycomb in mycomb];
在范围内（len（mycomb）-1，-1，-1）：
如果sum（mycomb [j]）== m：
myseq.append（mycomb [j ]）
return（myseq）
当我把 m = 270 （例如）它给了我：
[[114，156] ，[57，99，114]]
但从 myvar 表示还有其他组合的总和等于270.我在哪里无法理解。
TL
href =http://chat.stackoverflow.com/users/1903116/thefourtheye> thefourtheye ： def subsets_with_sum（lst，target，with_replacement = False）：
x = 0如果with_replacement else 1
def _a（idx，l，r，t）：
if t == sum（l） ：r.append（l）
eli f t < sum（l）：在范围（idx，len（lst））中返回
：
_a（u + x，l + [lst [u]]，r，t）
return r
return _a（0，[]，[]，target）
： ： ： ：<好吧 - 用一些逻辑快速和简单地应用你的数据得出结论：你有正确的答案： p>
＃data
vals = [57,71,87,97,109,101,103,113,114,115 ，128,129,131,137,147,156,163,186]
target = 270
>>>来自itertools导入组合
>>> （梳子）==目标]
[（114,156），（57,99,114）] $ b [comb for i in range（1,20）for comb in combinations（vals，i） $ b 然而，也许你想使用 combinations_with_replacement ，它允许从初始列表中多次使用值，而不是一次。
使用 itertools.combinations_with_replacement ：
>> > from itertools import combinations_with_replacement
>>> [comb for i in range（1,20）for comb in combination_with_replacement（vals，i）if sum（comb）== target]
>>> ＃结果需要太长时间...
您可以使它成为一个健壮的函数：
pre $ def $ subset_with_sum（lst，target，subset_lengths = range（1,20），method ='组合'）：
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）：
如果t == sum（l）：r.append（l）
elif t < sum（l）：返回
在范围内（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,109,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]]
$ b def _a（idx，l，r，t，w）：
if t == sum（l）：r.append（l）
elif t < sum（l）：返回
在范围内（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，如果sum（梳子）和comb（梳子）在
中，则getattr（itertools，method）（lst，i） ==目标]
vals = [57,71,87,97,109,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 （b（vals，270，method ='combinations_with_replacement'），from __main__ import vals，270，True），from __main__ import vals，a，number = 10）
print timeit b，数字= 10）
计时输出：
没有替换
0.0273933852733
0.683039054001
替换
0.0177899423427
...等了很长时间...没有结果...
结论：
新方法（a）至少快20倍。
I have series of numbers like this
myvar = [57, 71, 87, 97, 99, 101, 103, 113, 114, 115, 128, 129, 131, 137, 147, 156, 163, 186]
Now I want to calculate all such possible combinations (of length 1 to 20) whose sum is equal to a given number m.
I tried to solve with following code as :
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)
When I put m = 270 (for example) it gives me :
[[114, 156], [57, 99, 114]]
But is quite evident from the myvar that there are still other combinations which have a sum equal to 270. Where am I failing to comprehend.
TL;DR:
Discuss different methods, best method is listed here for ease of access and was originally written by 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)
note: the above method is modified with improvements from the original version below
Original Post:
Well - A quick and simple application of your data with some logic concludes that you have the correct answer:
# data
vals = [57, 71, 87, 97, 99, 101, 103, 113, 114, 115, 128, 129, 131, 137, 147, 156, 163, 186]
target = 270
Using 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)]
However, maybe you wanted to use combinations_with_replacement which lets values be used multiple times from the initial list as opposed to only once.
Using 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 ...
You can make it into a robust function:
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)]
Another method, provided by thefourtheye , it is much faster, and requires no imports:
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]]
Timing:
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)
Timing Output:
no replacement
0.0273933852733
0.683039054001
with replacement
0.0177899423427
... waited a long time ... no results ...
conclusion:
The new method (a) is at least 20 times faster.
这篇关于查找提供的Sum值的组合的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
