CODEWITHSUNDEEP
pythonnumpy
drum
drum

Reputation: 5651

Find all combination that sum to N with multiple lists

Given:

Want:

What I have:

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

Upvotes: 6

Views: 3263

Answers (3)

Stefan Pochmann
Stefan Pochmann

Reputation: 28596

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))

Upvotes: 11

Mijamo
Mijamo

Reputation: 3516

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)

Upvotes: 2

Ashish Kumar
Ashish Kumar

Reputation: 347

how about using "product" from itertools to get all possible m-length tuples. Then you just filter by the condition that the tuple sum == N

Upvotes: 1

Related Questions