get all integer partition of a number

Question

I basically have this question Get all numbers that add up to a number but I also need 0 to be included.

I have tried the accepted answer and made it start from 0, basically like

def sum_to_n(n, size, limit=None):
 """Produce all lists of `size` positive integers in decreasing order
 that add up to `n`."""
 if size == 1:
 yield [n]
 return
 if limit is None:
 limit = n
 start = 0
 stop = min(limit, n - size + 1) + 1
 for i in range(start, stop):
 for tail in sum_to_n(n - i, size - 1, i):
 yield [i] + tail

It worked out well for smaller numbers, but when I have larger numbers as targets it started to behave weird. For example:

for partition in sum_to_n(10,7):
 print(partition)

The output was like

0 0 0 0 0 0 10
1 0 0 0 0 0 9
1 1 0 0 0 0 8
1 1 1 0 0 0 7
1 1 1 1 0 0 6
1 1 1 1 1 0 5
1 1 1 1 1 1 4
2 0 0 0 0 0 8
2 1 0 0 0 0 7
2 1 1 0 0 0 6
2 1 1 1 0 0 5
2 1 1 1 1 0 4
2 1 1 1 1 1 3
2 2 0 0 0 0 6
2 2 1 0 0 0 5
2 2 1 1 0 0 4
2 2 1 1 1 0 3
2 2 1 1 1 1 2
2 2 2 0 0 0 4
2 2 2 1 0 0 3
2 2 2 1 1 0 2
2 2 2 1 1 1 1
3 0 0 0 0 0 7
3 1 0 0 0 0 6
3 1 1 0 0 0 5
3 1 1 1 0 0 4
3 1 1 1 1 0 3
3 1 1 1 1 1 2
3 2 0 0 0 0 5
3 2 1 0 0 0 4
3 2 1 1 0 0 3
3 2 1 1 1 0 2
3 2 1 1 1 1 1
4 0 0 0 0 0 6
4 1 0 0 0 0 5
4 1 1 0 0 0 4
4 1 1 1 0 0 3
4 1 1 1 1 0 2
4 1 1 1 1 1 1

Here it clearly didn't include the case of 5 5 0 0 0 0 0. Also it has repeat cases like 1 1 1 1 1 1 4 and 4 1 1 1 1 1 1 which i don't want. What is wrong with this code? How could I modify it or any other thoughts on how to solve the problem? Thanks!

• Shinra tensei: I see that some of these lists are repeated (although the numbers are in different order). Is that intended? Because the original answer is made so that this couldn't be a case.
• Irene Kara: Hm that's interesting, that was not my intention cuz i only need combinations for this step. I acc didn't find repeated cases, could you lmk which ones are repeated if you see any?
• Shinra tensei: 0 4 1 1 1 1 1 1, then a few more down below 0 1 1 1 1 1 1 4
• Irene Kara: Thanks a lot for pointing them out, I don't want repetitions as well

Answer 1

I think this is what you were going for:

def sum_to_n2(n, size, limit=None):
 if limit is None:
 limit = n
 if size == 1:
 if n <= limit:
 yield[n]
 else:
 for i in range(0, limit+1):
 for tail in sum_to_n2(n - i, size - 1, min(i, n-i)):
 yield[i] + tail
print(list(sum_to_n2(10, 7)))

The differences with your code:

• checking if limit is None at the start, the function has a simpler if .. else (mostly cosmetic, easier to understand I feel and no need for the return to get out of there);
• you always yield [n] if size == 1, but that should only happen if n <= limit;
• you compute a limit on the range as min(limit, n - size + 1) + 1, but that's hard to track mentally (more so as range stops just short of it); I just say that the limit is the minimum of i (the number we're adding to the sequence, so no larger numbers allowed anymore) and n-i (the remainder, we don't need bigger numbers than that anymore), and pass that to the recursive call with min(i, n-i).

I haven't done the full logic on where the computational error is in your code, but if I add the n <= limit condition to your code, it no longer includes zeroes. I'm sure you could figure it out when comparing values to my implementation of your algorithm, but I think mine is a bit cleaner anyway, so preferable.

Output for 6, 3 already shows a problem with your code, which is shorter than 10, 7. Your output for sum_to_n(5, 3):

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

Note the duplicates in there [2, 1, 2] and [2, 2, 1] for example.

My output for sum_to_n2(5, 3):

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

Personally, but this is purely style, I prefer the output of this modified implementation:

def sum_to_n2(n, size, limit=None):
 if limit is None:
 limit = n
 if size == 1:
 if n <= limit:
 yield[n]
 else:
 for i in range(limit, -1, -1):
 for tail in sum_to_n2(n - i, size - 1, min(i, n - i)):
 yield[i] + tail

Which results in (for sum_to_n2(5, 3)):

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

It does this by inverting the range in the for loop.

By the way, here's a non-recursive one-liner that does it, but it's slow as mud :):

def sum_to_n_one_liner (n, sized):
 set(tuple(sorted(t)) for t in filter(lambda s: sum(s) == n, product(*[range(n)]*size)))

It works by naively doing what needs to be done:

• take the numbers from 0 to n, size times
• compute the cartesian product, so you get all possible combinations of those numbers
• keep only the ones that sum up to n
• sort the resulting tuples and keep only unique ones

• Grismar: Note that this generates a list of lists, while the original linked question was asking for sets - however, OP was generating lists as well, and the quality of order not mattering was taking into account, so I chose lists as well.

Answer 2

In order to get no repeated partitions, you can define the function so that it only generates results that are in non decreasing order.

def partition(N,size):
 if size == 1 :
 yield (N,) # base case, only 1 part
 return
 for a in range(N//size+1): # smaller part followed by
 for p in partition(N-a*size,size-1): # equal or larger ones
 yield (a, *(n+a for n in p)) # recursing on delta only

Output:

for p in partition(10,7): print(p)
(0, 0, 0, 0, 0, 0, 10)
(0, 0, 0, 0, 0, 1, 9)
(0, 0, 0, 0, 0, 2, 8)
(0, 0, 0, 0, 0, 3, 7)
(0, 0, 0, 0, 0, 4, 6)
(0, 0, 0, 0, 0, 5, 5)
(0, 0, 0, 0, 1, 1, 8)
(0, 0, 0, 0, 1, 2, 7)
(0, 0, 0, 0, 1, 3, 6)
(0, 0, 0, 0, 1, 4, 5)
(0, 0, 0, 0, 2, 2, 6)
(0, 0, 0, 0, 2, 3, 5)
(0, 0, 0, 0, 2, 4, 4)
(0, 0, 0, 0, 3, 3, 4)
(0, 0, 0, 1, 1, 1, 7)
(0, 0, 0, 1, 1, 2, 6)
(0, 0, 0, 1, 1, 3, 5)
(0, 0, 0, 1, 1, 4, 4)
(0, 0, 0, 1, 2, 2, 5)
(0, 0, 0, 1, 2, 3, 4)
(0, 0, 0, 1, 3, 3, 3)
(0, 0, 0, 2, 2, 2, 4)
(0, 0, 0, 2, 2, 3, 3)
(0, 0, 1, 1, 1, 1, 6)
(0, 0, 1, 1, 1, 2, 5)
(0, 0, 1, 1, 1, 3, 4)
(0, 0, 1, 1, 2, 2, 4)
(0, 0, 1, 1, 2, 3, 3)
(0, 0, 1, 2, 2, 2, 3)
(0, 0, 2, 2, 2, 2, 2)
(0, 1, 1, 1, 1, 1, 5)
(0, 1, 1, 1, 1, 2, 4)
(0, 1, 1, 1, 1, 3, 3)
(0, 1, 1, 1, 2, 2, 3)
(0, 1, 1, 2, 2, 2, 2)
(1, 1, 1, 1, 1, 1, 4)
(1, 1, 1, 1, 1, 2, 3)
(1, 1, 1, 1, 2, 2, 2)

• cards: with functools.cache(partition) it runs even smoother
• Alain T.: Indeed, the recursive algorithm lends itself well to memoizing. But then it can't be a generator. Depending on requirements and size of the data, the higher memory usage for the cache may be a good trade off for better performance.
• cards: Interesting remark "But then it can't be a generator." but could you be more clearer? The cache decorator actually preserves the generator flavour of the function. In general, is a bad practice to post-process a generator recursive function?
• Alain T.: functools.cache does not store the values from a generator (values from yield). It stores the iterator that the function returns. Because you can only go through the iterator's data once, reusing the generator (from the cache) produces an empty/exhausted iterator. So the result of the "cached" recursive generator will not be complete.