Recursion Formula for Integer Partitions

Question

I have written the following code for evaluating integer partitions using the recurrence formula involving pentagonal numbers:

def part(n):
    p = 0
    if n == 0:
        p += 1
    else:
        k = 1
        while ((n >= (k*(3*k-1)/2)) or (n >= (k*(3*k+1)/2))):
            i = (k * (3*k-1)/2)
            j = (k * (3*k+1)/2)
            if ((n-i) >= 0):
                p -= ((-1)**k) * part(n-i)
            if ((n-j) >= 0):
                p -= ((-1)**k) * part(n-j)
            k += 1
    return p

    n = int(raw_input("Enter a number: "))
    m = part(n)
    print m

The code works fine up until n=29. It gets a bit slow around n=24, but I still get an output within a decent runtime. I know the algorithm is correct because the numbers yielded are in accordance with known values.

For numbers above 35, I don't get an output even after waiting for a long time (about 30 minutes). I was under the impression that python can handle numbers much larger than the numbers used here. Can someone help me improve my runtime and get better results? Also, if there is something wrong with the code, please let me know.

Padraic Cunningham · Accepted Answer · 2015-12-22 18:59:21Z

4

You can use Memoization:

def memo(f):
    mem = {}
    def wrap(x):
        if x not in mem:
            mem[x] = f(x)
        return mem[x]
    return wrap

@memo
def part(n):
    p = 0
    if n == 0:
        p += 1
    else:
        k = 1
        while (n >= (k * (3 * k - 1) // 2)) or (n >= (k * (3 * k + 1) // 2)):
            i = (k * (3 * k - 1) // 2)
            j = (k * (3 * k + 1) // 2)
            if (n - i) >= 0:
                p -= ((-1) ** k) * part(n - i)
            if (n - j) >= 0:
                p -= ((-1) ** k) * part(n - j)
            k += 1
    return p

Demo:

In [9]: part(10)
Out[9]: 42

In [10]: part(20)
Out[10]: 627

In [11]: part(29)
Out[11]: 4565

In [12]: part(100)
Out[12]: 190569292

With memoization we remember previous calculation so for repeated calculations we just do a lookup in the dict.

edited Dec 22, 2015 at 18:59

answered Dec 22, 2015 at 18:04

Padraic Cunningham

181k30 gold badges264 silver badges327 bronze badges

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

9 Comments

Nannu Over a year ago

for n=500, I'm getting a runtime error saying maximum recursion depth exceeded. Is there any way around this?

Padraic Cunningham Over a year ago

@Nannu, you can increase the recursion limit but really you would be better off implementing it iteratively. Python is not optimised for recursion

Padraic Cunningham Over a year ago

I can get to n =999, anything after that blows the stack

Nannu Over a year ago

I understand that recursion isn't really the best way to go in python, but I want to obtain the answers using recursion; I have another formula that doesn't use recursion, so I want to compare. Can you explain how increase the recursion limit?

Nannu Over a year ago

Yeah, I got upto n=500 until I got the error. This was after memoizing the function

|

Adam · Accepted Answer · 2015-12-22 18:45:36Z

0

Well there are a number of things you can do.

Remove duplicate calculations. - Basically you are calculating "3*k+1" many times for every execution of your while loop. You should calculate it once and assign it to a variable, and then use the variable.
Replace the (-1)**k with a much faster operation like something like -2*(k%2)+1). So instead of the calculation being linear with respect to k it is constant.
Cache the result of expensive deterministic calculations. "part" is a deterministic function. It gets called many times with the same arguments. You can build a hashmap of the inputs mapped to the results.
Consider refactoring it to use a loop rather than recursion. Python does not support tail recursion from what I understand, thus it is burdened with having to maintain very large stacks when you use deep recursion.

If you cache the calculations I can guarantee it will operate many times faster.

answered Dec 22, 2015 at 18:45

Adam

4163 silver badges6 bronze badges

2 Comments

Padraic Cunningham Over a year ago

I think the caching optimisation is pretty apparent from my answer, an iterative solution would probably be the only way to really improve the OP's own code outside of caching

Nannu Over a year ago

@Adam, I understand that recursion isn't really the best way to go in python, but I want to obtain the answers using recursion; I have another formula that doesn't use recursion, so I want to compare.

Collectives™ on Stack Overflow

Recursion Formula for Integer Partitions

2 Answers 2

9 Comments

2 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

9 Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related