CODEWITHSUNDEEP
pythonrecursion
DrDom
DrDom

Reputation: 4133

All permutations of integers corresponded to specific sum

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

Answers (2)

Louis Ricci
Louis Ricci

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

Martijn Pieters
Martijn Pieters

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

Related Questions