CODEWITHSUNDEEP
pythonrecursion
user1608392
user1608392

Reputation:

Unknown issue with recursive integer partition calculator in Python

I'm having some trouble with my recursive program to calculate the number of integer partitions of an integer.

Here's what I have written:

def p(k, n):
    if k > n:
        return 0
    if k == 1:
        return 1
    else:
        return (p(k+1, n) + p(k, n-k))

def partitions(n):
    ans = 1
    for k in range(1, n/2):
        ans += p(k, n-k)
    return ans

This algorithm is implemented from Wikipedia's article Partition (number theory). Here's what my program outputs for the first few integers:

partitions(0) = 1
partitions(1) = 1
partitions(2) = 1
partitions(3) = 1
partitions(4) = 2
partitions(5) = 2
partitions(6) = 2
partitions(7) = 2

I'm not sure why my program doesn't operate properly, since I thought I correctly implemented both recursion and the algorithm from Wikipedia. Could somebody help me understand what it's doing?

Upvotes: 2

Views: 244

Answers (2)

jason
jason

Reputation: 241641

You have one of the base cases wrong:

if k == 1:
    return 1

should be

if k == n:
    return 1

Additionally:

for k in range(1, n / 2):

should be

for k in range(1, n / 2 + 1):

This is because the sum in the formula is inclusive of the upper bound, but in Python, the range does not include the upper bound. Then:

print [partitions(i) for i in range(1, 8)]

gives

[1, 2, 3, 5, 7, 11, 15]

matching the values given in the Wikipedia article.

Upvotes: 2

DSM
DSM

Reputation: 353169

I see two problems:

This:

if k == 1:

should be if k == n:, and this loop:

for k in range(1, n/2):

should be range(1, n/2+1) -- or better, range(1, n//2+1) to be explicit about the fact we want integer division -- because range in Python doesn't include the upper bound. After fixing those, I get:

>>> [partitions(i) for i in range(1,10)]
[1, 2, 3, 5, 7, 11, 15, 22, 30]

(which, you'll notice, only has 9 values. :^)

Upvotes: 2

Related Questions