Hi,
I think a slightly mathematically enclined casual programmer is enough. And I think that algorithmics is indeed maths (and informatics), even though there certainly are forums that are more relevant for such questions.
About your problem. How would you procede "by hand"? Put a few balls in the first box (any number from 0 to n), then (among the remaining ones) put a few balls in the second ones, etc., until the last box where you put all the remaining balls.
If you have 4 boxes, you can do this with three nested "for" loops:
Code:
for i_1=0 to n
for i_2=n-i_1 to n
for i_3=n-i_1-i_2 to n
a solution is : i_1, i_2, i_3, n-i_1-i_2-i_3
end_for
end_for
end_for "Fine, you say, but what if I don't know k? How can I have my program do k-1 for-loops?".
Answer (a classical one): to overcome this problem, use a recursive function. The idea is that you make a function that calls itself, according to the following scheme :
Code:
function balls_in_boxes(n,k)
if k=1,
put the n balls in the only box
else,
for i=0 to n,
use balls_in_boxes(n-i,k-1) (it allows to put n-i balls in k-1 boxes)
and put i balls in the last box
end_for
end_if
end_function To make this more precise, you need the function to return the list of possible solutions. Depending on the programming language, this can be done in various ways.
Here is a working program in C language that I just wrote. It writes the solutions on the screen. You'll have to make a few changes if you want to store the configurations. In my function, I chose to give as an argument the positions of the balls that have been put before, so I can print them at the end. I put comments in the code.
Code:
#include <stdio.h>
#include <stdlib.h>
// Lists on the screen the different Ways to put n balls in k(>=1) boxes (empty boxes allowed), followed by the "nb" numbers given by the array "start" (useful for recursion) ; returns the number of solutions
// So if we only want the ways to put n balls in k boxes, we choose nb=0 and "start" is any pointer (for instance, the NULL pointer will do fine)
int balls_in_boxes(int n,int k,int *start,int nb)
{
int i,j,total;
int *start2;
if(k==1)
{
// Just print the given starting numbers and put the balls in the only box
i=0;
while(i<nb)
{
printf("%d ",start[i]);
i++;
}
printf("%d\n", n);
return 1;
}
else
{
// Choose the number i (0<=i<=n) of balls to put in the first box, and call the function on the next k-1 boxes for n-i balls.
total=0;
for(i=0;i<=n;i++)
{
// Make an array of size nb+1 to store the position of balls
start2=malloc((nb+1)*sizeof(int));
// Copy "start" into the first nb cells of "start2"
for(j=0;j<nb;j++)
start2[j]=start[j];
// Add a new cell with i balls
start2[nb]=i;
total += balls_in_boxes(n-i,k-1,start2,nb+1); // Print what we want, and count
free(start2);
}
return total;
}
}
int main(void)
{
int n,k,total;
n=3; k=3;
total=balls_in_boxes(n,k,NULL,0);
printf("\nNumber of solutions : %d\n",total);
exit(0);
}
LinkBack URL
About LinkBacks
Originally Posted by cduston 
