How to get this list of combinations?

Question

I have two numbers, N and L (let's say 5 and 3).

How can I generate every possible list where the sum of the list is equal to N (5) and the length of every list is L (3)?

Example output (in this case):

[0, 0, 5]
[0, 1, 4]
[0, 2, 3]
[0, 3, 2]
...
[0, 5, 0]
...
[1, 4, 0]
...
[5, 0, 0]

I've checked out itertools and its combinations and permutations functions, but they don't seem right for the task.

@Colin Yes, N, L and the numbers in the list can only be positive (otherwise there'd be infinite possible lists!) — Adi219, Apr 29 '18 at 16:28
You tried several things but they don't seem "right". Why not? — Jongware, Apr 29 '18 at 16:29
To all close/down voters, I don't see how this question is 'too broad', as the requirements are quite clear and are understandable. — Adi219, Apr 29 '18 at 16:31
Possible duplicate: [Generate all possible lists of length N that sum to S in Python](https://stackoverflow.com/questions/7748442/generate-all-possible-lists-of-length-n-that-sum-to-s-in-python) — miradulo, Apr 29 '18 at 16:32
@usr2564301 Permutations wasn't helping me for the 'sum' restriction, and combinations didn't seem to match my expected output either... — Adi219, Apr 29 '18 at 16:32

Ajax1234 · Accepted Answer · 2018-04-29T16:51:52.853

You can create a recursive function to generate all possible permutations with the given conditions, and then filter to retain only the lists which sum to the desired value:

def list_results(a, b):
   return [i for i in permutations(b) if sum(i) == a]

def permutations(d, current = []):
   if len(current) == d:
     yield current
   else:
     for i in range(10):
        yield from permutations(d, current+[i])

print(list_results(5, 3))

Output:

[[0, 0, 5], [0, 1, 4], [0, 2, 3], [0, 3, 2], [0, 4, 1], [0, 5, 0], [1, 0, 4], [1, 1, 3], [1, 2, 2], [1, 3, 1], [1, 4, 0], [2, 0, 3], [2, 1, 2], [2, 2, 1], [2, 3, 0], [3, 0, 2], [3, 1, 1], [3, 2, 0], [4, 0, 1], [4, 1, 0], [5, 0, 0]]

Edit: a slightly faster would entail an additional check in the recursive function:

import time
def timeit(f):
   def wrapper(*args, **kwargs):
      c = time.time()
      results = list(f(*args, **kwargs))
      print("Result from function '{}' achieved in {}".format(f.__name__, abs(c-time.time())))
      return results
   return wrapper

@timeit
def outer_permutations():
   def permutations1(d, b, current = []):
     if len(current) == d:
       yield current
     else:
       for i in range(10):
         if len(current) < 2 or sum(current+[i]) == b:
           yield from permutations1(d, b, current+[i])
   yield from permutations1(3, 5)

@timeit
def list_results(a, b):
   return [i for i in permutations(b) if sum(i) == a]


v = outer_permutations()
v1 = list_results(3, 5)

Output:

Result from function 'outer_permutations' achieved in 0.0006079673767089844
Result from function 'list_results' achieved in 0.09148788452148438

Note that the output from both functions is:

[[0, 0, 5], [0, 1, 4], [0, 2, 3], [0, 3, 2], [0, 4, 1], [0, 5, 0], [1, 0, 4], [1, 1, 3], [1, 2, 2], [1, 3, 1], [1, 4, 0], [2, 0, 3], [2, 1, 2], [2, 2, 1], [2, 3, 0], [3, 0, 2], [3, 1, 1], [3, 2, 0], [4, 0, 1], [4, 1, 0], [5, 0, 0]]

Thanks! I'll try this now ... is there a way to make this more efficient? (as N can be in the hundreds) — Adi219, Apr 29 '18 at 16:27
@Adi219 Yes, there is - see the answer on the linked duplicate :) — miradulo, Apr 29 '18 at 16:36
@Adi219 Please see my recent edit. I added a slightly faster method, along with the total timings for both methods. — Ajax1234, Apr 29 '18 at 16:39

How to get this list of combinations?

1 Answers1