Find all combination that sum to N with multiple lists

Question

Given:

• m number of lists (m can vary).
• Each list contain arange() of numbers.

Want:

• Find the m-tuple (one number per list) that sum() to N.

What I have:

• I can find all combination in a static number of lists.

  import numpy as np
  for a in np.arange(0,1,0.01):
      for b in np.arange(0,1,0.01):
          for c in np.arange(0,1,0.01):
              for d in np.arange(0,1,0.01):
                  if (a+b+c+d) == 1.0: 
                      print a,b,c,d
  

I would also like to find an optimal way to compute this as well.

Answer 1

As discussed in the comments, the ranges are all the same and we ought to use integers. Here's an imho neat way then.

Instead of producing four numbers and testing whether they add up to 10, produce three numbers defining a partition of the interval [0, 10] into four intervals. For example when we have the cuts at (3, 4, 8), and we add the end points 0 and 10, then we have the boundaries (0, 3, 4, 8, 10). The differences between adjacent boundaries are (3-0, 4-3, 8-4, 10-8) = (3, 1, 4, 2). That's four numbers adding up to 10. Here's code doing that:

n = 10
import itertools, operator
for cuts in itertools.combinations_with_replacement(range(n+1), 3):
    combi = list(map(operator.sub, cuts + (n,), (0,) + cuts))
    if max(combi) < n:
        print(combi)

That prints:

[0, 0, 1, 9]
[0, 0, 2, 8]
[0, 0, 3, 7]
[0, 0, 4, 6]
[0, 0, 5, 5]
[0, 0, 6, 4]
[0, 0, 7, 3]
[0, 0, 8, 2]
[0, 0, 9, 1]
[0, 1, 0, 9]
[0, 1, 1, 8]
[0, 1, 2, 7]
...
...
[7, 2, 0, 1]
[7, 2, 1, 0]
[7, 3, 0, 0]
[8, 0, 0, 2]
[8, 0, 1, 1]
[8, 0, 2, 0]
[8, 1, 0, 1]
[8, 1, 1, 0]
[8, 2, 0, 0]
[9, 0, 0, 1]
[9, 0, 1, 0]
[9, 1, 0, 0]

It's very efficient, since it produces the combinations pretty directly. The if max(combi) < n only filters out [0, 0, 0, 10], [0, 0, 10, 0], [0, 10, 0, 0] and [10, 0, 0, 0].

---

Here's a speed comparison between your original, mine, and @Mijamo's, with a range of 100 numbers like in your example:

  drum: 21.027 seconds
Stefan:  0.708 seconds
Mijamo: 62.864 seconds

Full code for that test:

import itertools, operator
from timeit import timeit

def drum(n):
    out = []
    for a in range(n):
        for b in range(n):
            for c in range(n):
                for d in range(n):
                    if a + b + c + d == n:
                        out.append((a, b, c, d))
    return out

def Stefan(n):
    combinations = (map(operator.sub, cuts + (n,), (0,) + cuts)
                    for cuts in itertools.combinations_with_replacement(range(n+1), 3))
    return [c for c in combinations if max(c) < n]

def Mijamo(n):
    combinations = itertools.product(range(n), repeat=4)
    return [tuple for tuple in combinations if sum(tuple) == n]

for func in drum, Stefan, Mijamo:
    print '%6s: %6.3f seconds' % (func.__name__, timeit(lambda: func(100), number=1))

Answer 2

All the combinations can be retrieved this way:

combinations = itertools.product(np.arange(0,1,0.01), repeat = m)

https://docs.python.org/3.5/library/itertools.html#itertools.product

And as it is a generator, you can then make a new generator to return the tupples that sum to n this way

results = (tuple for tuple in combinations if sum(tuple) == N)