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!
CodePudding user response：
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 Noneat the start, the function has a simplerif .. else(mostly cosmetic, easier to understand I feel and no need for thereturnto get out of there); - you always yield
[n]ifsize == 1, but that should only happen ifn <= 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 ofi(the number we're adding to the sequence, so no larger numbers allowed anymore) andn-i(the remainder, we don't need bigger numbers than that anymore), and pass that to the recursive call withmin(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,sizetimes - 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
CodePudding user response：
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)