Finding Combinations to the provided Sum value

by

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.

More Related Contents:

  1. Python for in range()
  2. How are lambdas useful? [closed]
  3. Apply function to each element of a list
  4. python max function using ‘key’ and lambda expression
  5. Why does Python code use len() function instead of a length method?
  6. Calling variable defined inside one function from another function
  7. Find all combinations of a list of numbers with a given sum
  8. Why do some functions have underscores “__” before and after the function name?
  9. What are good uses for Python3’s “Function Annotations”?
  10. Defining private module functions in python
  11. Difference between returns and printing in python? [duplicate]
  12. How to pass an operator to a python function?
  13. How can I pass information (a variable) out of a function? How can I use that from outside, e.g. in other functions?
  14. How do I pass variables across functions?
  15. How to make a local variable (inside a function) global [duplicate]
  16. Python passing list as argument
  17. Is it pythonic for a function to return multiple values?
  18. How to pass dictionary items as function arguments in python? [duplicate]
  19. What is a maximum number of arguments in a Python function?
  20. int([x[, base]]). Square brackets in functions in Python documentation? [duplicate]
  21. Numpy: efficient way to generate combinations from given ranges
  22. function is not defined error in Python
  23. Why is “None” printed after my function’s output?
  24. How does Python return multiple values from a function?
  25. Get all possible (2^N) combinations of a list’s elements, of any length
  26. Is it possible to not return anything from a function in python? (What happens if the function reaches the end without `return`ing?)
  27. python all possible combinations of 0,1 of length k [duplicate]
  28. Modify global list inside a function
  29. Sort python list by function
  30. counting combinations and permutations efficiently

Leave a Comment