5
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);
}
Prasoon Saurav
  • 91,295
  • 49
  • 239
  • 345
F. P.
  • 5,018
  • 10
  • 55
  • 80
  • 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];` – user2448431 Oct 21 '16 at 11:17

2 Answers2

4

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];
CygnusX1
  • 20,968
  • 5
  • 65
  • 109
3

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.

vhallac
  • 13,301
  • 3
  • 25
  • 36