I'm trying to re-build the following formula for 'Restricted number of parts and restricted size of parts' from the oeis.org website:

It is supposed to give the "Compositions of n   ≤   k   ≤   m n into n parts, with size of parts not greater than m". I'm looping through the code until I get back a 0.

The expected outcome for C_3(3, 3) is 1,3,6,7,6,3,1 (as shown in the table on the site). I'm getting something like 1369121212

I just don't see where my code is wrong. I've looked at it for about 2 days now and still don't get it.

#include <iostream>

int C(int m, int n, int j)
{
    if (n == 0 && j == 0)
    {
        return 1;
    }
    if (j < 0 || j > (m - 1) * n)
    {
        return 0;
    }

    int sum = 0;
    for (int i = j - ((m - 1) * n); i <= j;   i)
    {
        sum  = C(m, n - 1, i);
    }
    return sum;
}

int main()
{
    constexpr int m = 3;
    constexpr int n = 3;

    int counter = 0;
    while (int result = C(m, n, counter  ))
    {
        std::cout << result;
    }

    std::cin.ignore();

    return 0;
}

CodePudding user response：

So it's a recursive function for generating the number of restricted compositions of m elements into n parts of size at most m but the formula for this function seems to be incorrect.

The recursive formula should be:

C(m, n, j) = C(m, n-1, j-1)   C(m, n-1, j-2)   ...   C(m, n-1, j-m)

for a given value of n, the number of compositions of m elements into n parts of size at most m is equal to the number of compositions of m-1 elements into n-1 parts of size at most m, plus the number of compositions of m-2 elements into n-1 parts of size at most m, and so on, up to the number of compositions of 0 elements into n-1 parts of size at most m.

The base case of the recursion is when n = 0 and j = 0, in which case the function should return 1 (since there is only one way to compose 0 elements into 0 parts). The function should return 0 if either n < 0 or j < 0, since these cases are not valid.

#include <iostream>

int C(int m, int n, int j)
{
    if (n == 0 && j == 0)
    {
        return 1;
    }
    if (n < 0 || j < 0)
    {
        return 0;
    }

    int sum = 0;
    for (int i = j; i >= j - m   1; --i)
    {
        sum  = C(m, n - 1, i);
    }
    return sum;
}

int main()
{
    constexpr int m = 3;
    constexpr int n = 3;

    int counter = 0;
    while (int result = C(m, n, counter  ))
    {
        std::cout << result << " ";
    }

    std::cin.ignore();

    return 0;
}

check for j > (m-1)*n should be included:

int C(int m, int n, int j)
{
    if (n == 0 && j == 0)
    {
        return 1;
    }
    if (n < 0 || j < 0 || j > (m - 1) * n)
    {
        return 0;
    }

    int sum = 0;
    for (int i = j; i >= j - m   1; --i)
    {
        sum  = C(m, n - 1, i);
    }
    return sum;
}