Practising dynamic programming

Arrangements, combinations and permutations, probability, ...
Post Reply
bentaylortheonly
Posts: 3
Joined: Wed Jan 17, 2018 7:39 pm

Practising dynamic programming

Post by bentaylortheonly » Sat Jan 27, 2018 1:13 pm

Just trying to get the hang of DP and how to be able to generically apply it to any situation.
I've read a few examples of algorithms to solve problems using DP but slightly struggling to see how to apply it to a given, new, problem.

So supposing the problem was: given a set of integers {1,2,3,...,N}
let S(N) be the number of subsets of those integers that add up to N. Each integer, let's call it i, in the subset can only be used once. (This might actually be similar to an existing PE problem but it's not intended to be, I just made it up to test the technique)
So for instance:
S(1)=1 (the set is {1})
S(2)=1 {2}
S(3)=2 {1,2} and {3}
S(6)=4 {1,2,3} , {1,5}, {2,4}, {6}.
S(10)=10 {10}, {1,9}, {2,8}, {3,7}, {4,6}, {1,2,7}, {1,3,6}, {1,4,5}, {2,3,5}, {1,2,3,4}.

So my, obviously currently flawed, process of generating this algorithm was this:
Consider each i. Find the maximum number ('max') that can be created with integers up to i.
So when i=3, max=1+2+3. When i=4, max=10 as we could have a subset of 1+2+3+4. etc.
Add one to to w[j] for each integer j from i to max. Rationale: using i adds one more possibility to the number of ways of creating each j.

And I came up with this:

Code: Select all

def S(N):
    w = [0]*(N+1); #w[n] = the number of ways of making n
    max = 0
    for i in range(1, N+1): #i is the next number in the subset
        max += i #the max number we can make with numbers up to i
        if max>=N:
            max = N
            
        for j in range(i, max+1):
            w[j]+=1 # using i adds one more possibility to the ways of making j.
                
    return w
        
print(S(10))        
The algorithm produces
{0, 1, 1, 2, 2, 3, 4, 4, 5, 6, 7}
but it should be
{0, 1, 1, 2, 2, 3, 4, 5, 6, 8, 10}

There's obviously some fundamental flaw in this logic but I'm struggling to see what the correction is.
I keep thinking that the flaw is due to miscounting subsets with 3 or more elements in them, which start at S(6). But my algorithm is correct up to and including S(6) - it only starts giving the wrong answer from S(7) on.

It must be something to do with referring back to previous stored values. Can anyone be so kind as to venture a clear explanation of how to modify the algorithm to be correct?

traxex
Posts: 77
Joined: Thu Oct 19, 2017 12:30 pm

Re: Practising dynamic programming

Post by traxex » Sat Jan 27, 2018 2:44 pm

Here is a slightly modified version that works, except that it gives S(0) = 1 using the empty subset.

Code: Select all

def S(N):
    w = [0]*(N+1)
    w[0] = 1
    for i in range(1, N+1):
        for j in reversed(range(i, N+1)):
            w[j] += w[j - i]
    return w

print(S(10))
The variable "max" is a valid optimization, but it is not necessary.

It's crucial to increment w[j] with the value of w[j-i] instead of 1. It's also important to loop backwards when modifying "w" in-place. Otherwise, during the iteration i==3, we would first add w[0] to w[3], then we'd add w[3] to w[6], etc., essentially counting subsets with multiple copies of 3.

Looping in increasing order can be made to work with a temporary array:

Code: Select all

def S2(N):
    w = [0]*(N+1)
    w[0] = 1
    for i in range(1, N+1):
        w2 = w[:]
        for j in range(i, N+1):
            w2[j] += w[j - i]
        w = w2
    return w
Technically, everyone is full of himself.

bentaylortheonly
Posts: 3
Joined: Wed Jan 17, 2018 7:39 pm

Re: Practising dynamic programming

Post by bentaylortheonly » Sat Jan 27, 2018 2:52 pm

Excellent, thanks very much for that, I'll digest that and hopefully be able to create my own in future.

MuthuVeerappanR
Posts: 315
Joined: Sun Mar 22, 2015 2:30 pm
Location: India
Contact:

Re: Practising dynamic programming

Post by MuthuVeerappanR » Sat Jan 27, 2018 2:58 pm

I'm not expert in DP either but this problem can be solved in a couple of ways. The problem at hand is well known and studied. You are asking for the number of partitions with distinct summands. My favorite would be to use generating functions.

Let $f(x)=(1+x)(1+x^2)(1+x^3)(1+x^4)\cdots$

What does the coefficient of $x^n$ represent when we expand this?? Here are the coefficients using Wolfram Alpha.

To turn into a DP approach, let $f(n,k)$ represent the number of partitions of $n$ using numbers upto $k$. In gen functions, let

$f_k(x)=\displaystyle\prod_{i=1}^k(1+x^i)$

The coefficients of $x^n$ is $f_k(x)$ is then $f(n,k)$.

Also, $f_k(x)=f_{k-1}(x)(1+x^k)$. If we equate the coefficients of $x^n$ on both sides we get, $f(n,k)=f(n,k-1)+f(n-k,k-1)$.

As no summand can exceed $n$ in a partition of $n$, $f(n,n)$ gives the answer we are looking for.

Of course, there are much more general cases where the gen. functions may not be easy to come up with but still it helped me solve a lot of PE problems. You can also check Partitions (Number Theory) for more on the problem you are looking for and Analytic Combinatorics to know more about gen. functions.

Happy Solving!!
Image
It is not knowledge, but the act of learning, not possession but the act of getting there, which grants the greatest enjoyment.

Post Reply