# Dynamic programming: Number of ways of partitioning a set of numbers

Discussion in 'Programming/Internet' started by Lee Xing, Oct 8, 2018.

1. While reading an algorithm book, I found the following exercise.

Given a set of n elements, write an algorithm that finds number of ways of partitioning it. Example: When n = 2, there are 2 ways of partitioning the set(into two sets with one element, or into the original set and the empty set).

And instead of the algorithm, I tried the python code using dynamic programming.

def ways(n):
dp = *(n+1),
sum = *(n+1) ## declaring 2 arrays of n+1 size
dp = 0
dp = 1
sum = 0
sum = 1
lastcalc = 1 # last calculated var
for i in range (2,n):
if lastcalc < i/2 :
for j in range (lastcalc, i/2):
sum[j] = sum[j-1] + dp[j]
lastcalc = (i/2) # update the lastcalculated variable
dp = sum[i/2]
return dp[n]

print(ways(2))

According to the book, print(ways(2)) supposed to give me 2 but my code is giving me 0.

My question: how can I fix this? What could be an efficient pseudocode for the question (dynamic programming)?

Thanks in advance for any help.