How can I better optimize my program for partitioning a given sum? (Python)

Question

If you are not familiar with partitions, I advise you visit this page. It explains it nicely: https://en.m.wikipedia.org/wiki/Partition_(number_theory)

For some context, the problem I am trying to solve involves partitioning: I am trying to return the number of possible partitions of integers that add to a given sum that has no duplicate integers.

Here is a quick example: if you input 10, the partitions (9,1) and (8,2) would count because each value is unique, and the sum of the partitions is 10. However, if the partition is something like (5,2,1,1,1,) it will not pass since once it is broken down into just its unique values, it is (5,2,1,), which does not add to 10.

I coded a solution that gets the job done with lower numbers, like 10. However, the problem has a test case of 200, and it is taking a very long time to run.

I know that the problem is that partitioning is inherently exponential, but I don't think it is within my capabilities to come up with a way to optimize the code I have.

Here is my code:

def solution(n):
    arr = []
    count = 0
    def partitions(num, I=1):
        yield (num,)
        for i in range(I, num//2 + 1):
            for p in partitions(num-i, i):
                yield (i,) + p

    arr = list(partitions(n))

    for part in arr:
        if sum(sorted(list(set(part)))) ==  n and len(part) > 1:
            count += 1

return count

#input: 10 ---> output: 9
#input: 3 ---> output: 1
#input: 50 ---> output: 3657

The answer and OEIS sequence is in the wikipedia article you linked to. — Dave
– Dave, Commented Jun 11, 2020 at 3:57

MBo · Accepted Answer · 2020-06-11 04:05:05Z

2

Counting partitions of integer into distinct parts using built-in Python memoization tool (works fast for argument 200).

OEIS sequence for reference

Result is one more than yours because one-part partition is counted too (3 -> 3, 2+1).

import functools

@functools.lru_cache(maxsize=None)
def growparts(n, last = 0):
    if n == 0:
        return 1
    result = 0
    for i in range(last + 1, n + 1):
        result += growparts(n - i, i)
    return result

print(growparts(50))

>>>  3658

edited Jun 11, 2020 at 4:05

answered Jun 11, 2020 at 3:58

MBo

80.7k5 gold badges61 silver badges99 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

MBo Over a year ago

@Dave Yes, hand-printed typo

Collectives™ on Stack Overflow

How can I better optimize my program for partitioning a given sum? (Python)

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related