Finding number of integer partitions with efficient way

Asked Jul 30 '17 at 05:07

Active Jul 30 '17 at 05:21

Viewed 102 times

I am trying to find number of integer partitions of given n - number. If I have n == 4, the answer should be 5 because:

4 = 1+1+1+1
4 = 2+1+1
4 = 3+1
4 = 2+2
4 = 4

My code works properly but the matter is that it counts big numbers for a very long time. I have no idea how to optimize my code. Maybe you can help me to make it faster?

def get_answer(n):
    if n == 0:
        yield []
        return
    for p in get_answer(n-1):
        yield [1] + p
        if p and (len(p) < 2 or p[1] > p[0]):
            yield [p[0] + 1] + p[1:]
number_of_partitions=lambda n:sum(1 for _ in get_answer(n))

edited Jul 30 '17 at 05:21

miradulo

28,857
6
80
93

asked Jul 30 '17 at 05:07

Nikita.K

1

This might be better suited for CodeReview I think. – miradulo Jul 30 '17 at 05:11
1

If you want to get it really fast, you should consider adding a [table](https://oeis.org/A000041). – U2EF1 Jul 30 '17 at 05:12
@Mitch, Elegant Python code for Integer Partitioning works slower than mine – Nikita.K Jul 30 '17 at 05:24
@Nikita.K If you look a bit farther down on the linked duplicate, see http://jeromekelleher.net/generating-integer-partitions.html – miradulo Jul 30 '17 at 05:25
@Mitch, I checked accel_asc. It works a bit faster but it takes more memory – Nikita.K Jul 30 '17 at 05:52
@Nikita.K I encourage you to check out the CodeReview stack exchange site, it might be a good fit! – miradulo Jul 30 '17 at 05:53

Finding number of integer partitions with efficient way

0 Answers0