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;
}
>Solution :
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;
}