CODEWITHSUNDEEP
pythonrecursion
Nannu
Nannu

Reputation: 33

Recursion Formula for Integer Partitions

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.

Upvotes: 3

Views: 705

Answers (2)

Padraic Cunningham
Padraic Cunningham

Reputation: 180550

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.

Upvotes: 4

Adam
Adam

Reputation: 416

Well there are a number of things you can do.

  1. 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.

  2. 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.

  3. 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.

  4. 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.

Upvotes: 0

Related Questions