Find values in a list that add up to a given value
I am trying to code something simple and pythonic for defining combinations of values from a list that add up to a specific value, within some tolerance.
For example:
if A=[0.4,2,3,1.4,2.6,6.3]
u is target value 5 +/- 0.5
then i want to get (2,3), (1.4,2.6), (2,2.6), (0.4,2,3), (0.4,3,1.4)
etc, if no combinations are found then function should return 0 or nothing or something like that.
Any help would be greatly appreciated.
+3
source to share
2 answers
Here's a recursive approach:
# V is the target value, t is the tolerance
# A is the list of values
# B is the subset of A that is still below V-t
def combination_in_range(V, t, A, B=[]):
for i,a in enumerate(A):
if a > V+t: # B+[a] is too large
continue
# B+[a] can still be a possible list
B.append(a)
if a >= V-t: # Found a set that works
print B
# recursively try with a reduced V
# and a shortened list A
combination_in_range(V-a, t, A[i+1:], B)
B.pop() # drop [a] from possible list
A=[0.4, 2, 3, 1.4, 2.6, 6.3]
combination_in_range(5, 0.5, A)
+2
source to share
Take a look at itertools.combinations
def first_attempt(A=A):
for i in xrange(1,len(A)+1):
print [comb
for comb in list(itertools.combinations(A,i))
if 4.5 < sum(map(float, comb)) < 5.5
]
## -- End pasted text --
In [1861]: %timeit first_attempt
10000000 loops, best of 3: 29.4 ns per loop
Output -
In [1890]: first_attempt(A=A)
[]
[(2, 3), (2, 2.6)]
[(0.4, 2, 3), (0.4, 2, 2.6), (0.4, 3, 1.4)]
[]
[]
[]
+5
source to share