Dynamic programming approach to calculating Stirling's Number

Question

int s_dynamic(int n,int k) {
    int maxj = n-k;

    int *arr = new int[maxj+1];

    for (int i = 0; i <= maxj; ++i)
        arr[i] = 1;

    for (int i = 1; i <= k; ++i)
        for(int j = 1; j <= maxj; ++j)
            arr[j] += i*arr[j-1];

    return arr[maxj];
}

Here's my attempt at determining Stirling numbers using Dynamic Programming.

It is defined as follows:

S(n,k) = S(n-1,k-1) + k S(n-1,k), if 1 < k < n

S(n,k) = 1, if k=1 ou k=n

Seems ok, right? Except when I run my unit test...

partitioningTest ..\src\Test.cpp:44 3025 == s_dynamic(9,3) expected:    3025    but was:    4414    

Can anyone see what I'm doing wrong?

Thanks!

BTW, here's the recursive solution:

int s_recursive(int n,int k) {
    if (k == 1 || k == n)
        return 1;

    return s_recursive(n-1,k-1) + k*s_recursive(n-1,k);
}

Basidiospore

Oh, just in case, these are for Stirling numbers of the second kind. If you want the first kind there's a signed recurrence such that arr[j] -= (i+j+1)*arr[j-1]. It also requires beginning the sequence with arr all zeros except the first element, i=1 as it originally was, and the the returned value must be (arr[maxj]<0) ? -arr[maxj] : arr[maxj]; – Stepfather

Answer 1

Found the bug. You already computed your dynamic array of Stirlings numbers for k=1 (S(n,1)=1 for all n). You should start computing S(n,2) - that is:

for (int i = 2; i <= k; ++i) //i=2, not 1
  for(int j = 1; j <= maxj; ++j)
    arr[j] += i*arr[j-1];

Lonnielonny

Answer 2

Your approach is just fine, except you seem to have made a simple indexing error. If you think about what indexes i and j represent, and what the inner loop transforms arr[j] to, you'll see it easy enough (I lie, it took me a good half hour to figure out what was what :)).

From what I can decode, i represents the value k during calculations, and arr[j] is transformed from S(i+j, i-1) to S(i+1+j, i). The topmost for loop that initializes arr sets it up as S(1+j, 1). According to these loops, the calculations look just fine. Except for one thing: The very first i loop assumes that arr[j] contains S(0+j, 0), and so it is where your problem lies. If you change the starting value of i from 1 to 2, all should be OK (you may need an if or two for edge cases). The initial i=2 will transform arr[j] from S(1+j, 1) to S(2+j, 2), and the rest of the transformations will be just fine.

Alternatively, you could have initialized arr[j] to S(0+j, 0) if it were defined, but unfortunately, Stirling's numbers are undefined at k=0.

EDIT: Apparently I was wrong in my last comment. If you initialize arr to {1, 0, 0, ...}, you can leave starting value of i as 1. For this, you use the initial values S(0, 0)=1, and S(n, 0)=0, n>0 instead.

Darlington

Your answer provided me with a lot of info, but the accepted one was more on point. Thanks and sorry. – Basidiospore

No worries, he made it there first in any case. :) – Darlington

@Darlington You said arr[j] is transformed from S(i+j, i-1) to S(i+1+j, i) but it should be transformed from S(i+j-1, i-1) to S(i+j, i) – Rosemaryrosemond