Reputation: 4133
I wanted to generate all permutations from the list of integers [3,5,7,9]
which resulted in a specific sum value 15
. I implemented this, it's OK.
def add_next(seq, count, m):
s = sum(seq)
if s == m:
count += 1
print(seq)
elif s < m:
for i in [3,5,7,9]:
add_next(seq + [i], count, m)
else:
return count
add_next([], 0, 15)
Output:
[3, 3, 3, 3, 3]
[3, 3, 9]
[3, 5, 7]
[3, 7, 5]
[3, 9, 3]
[5, 3, 7]
[5, 5, 5]
[5, 7, 3]
[7, 3, 5]
[7, 5, 3]
[9, 3, 3]
The problem is how to re-write this function to return just the number of possible permutations as a function result? Since for huge lists and big sum values it's not reasonable to generate all string outputs. I don't fully understand how to pass values inside and outside recursive function.
I tried:
def add_next2(seq, count, m):
s = sum(seq)
if s == m:
count += 1
print(seq)
elif s < m:
for i in [3,5,7,9]:
count = add_next2(seq + [i], count, m)
else:
return count
add_next([], 0, 15)
but it retuns an error TypeError: unsupported operand type(s) for +=: 'NoneType' and 'int'
. So count
is None
. Why?
Another option is how to re-write this function to transform it to the generator and yield the output strings one after another?
Upvotes: 2
Views: 880
Reputation: 21116
If you're just counting successful recursive results, you don't need 'count' as a parameter. You can just return the successful results as 1 and unsuccessful as 0, letting them accumulate.
EDIT 2 A little more concise but still readable
def add_next(seq, m):
s = sum(seq)
count = 1 if s == m else 0
if s < m:
for i in [f for f in [3,5,7,9] if s + f <= m]:
count += add_next(seq + [i], m)
return count
print(add_next([], 15))
EDIT You can also filter your [3,5,7,9] list so that your for i in loop only deals with elements that have a possibility of success.
for i in [f for f in [3,5,7,9] if s + f <= m]:
Upvotes: 1
Reputation: 1125398
Your recursive function doesn't return a value for s <= m
. Return something from your function for those cases, otherwise None
is returned instead.
Most likely you want to return count
in all cases:
def add_next2(seq, count, m):
s = sum(seq)
if s == m:
count += 1
elif s < m:
for i in [3,5,7,9]:
count = add_next2(seq + [i], count, m)
return count
This then works:
>>> def add_next2(seq, count, m):
... s = sum(seq)
... if s == m:
... count += 1
... elif s < m:
... for i in [3,5,7,9]:
... count = add_next2(seq + [i], count, m)
... return count
...
>>> add_next2([], 0, 15)
11
Upvotes: 1