1. This site uses cookies. By continuing to use this site, you are agreeing to our use of cookies. Learn More.

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

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

  1. Lee Xing

    Lee Xing Guest

    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 = [0]*(n+1),
    sum = [0]*(n+1) ## declaring 2 arrays of n+1 size
    dp[0] = 0
    dp[1] = 1
    sum[0] = 0
    sum[1] = 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]


    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.

    Login To add answer/comment

Share This Page