The problem I need to solve is simple to expose. Given two strictly positive integers m and n, I want to generate and count all the matrix of dimension m (that is arrays with m lines and m columns) such that both
* each element is non negative
* the sum of elements in every line and in every column equals n.
I wrote pograms that generate and count these matrix for n as a variable but not for any dimension m. Here are programs for m=3 and for m=4. It works for any value of m.
Does anyone have a suggestion that would allow me to write a general program that works for any value of n ? How can I avoid the fact that the number of loops increases dramaticaly with n ?? Any suggestion would be of great help to me.
first program : for m=3 :
#include <iostream.h>
int max(int,int);
int main()
{
unsigned long u; // counter of matrix of dimension 3 with the
// two properties
int n; // dimension
cout<<"m=3. Enter n, the dimension of the matrix :";
cin>>n;
int c[1][1]; // c denotes any matrix with dimension m=3
//property of the sum enables us to work with a
// reduced dimension (2 instead of 3)
for (c[0][0]=0; c[0][0]<=n; c[0][0]++)
{
for (c[0][1]=0; c[0][1]<=n-c[0][0]; c[0][1]++)
{
for (c[1][0]=0; c[1][0]<=n-c[0][0]; c[1][0]++)
{
for c[1][1]=0;c[1][1]<=n-max(c[0][1], c[1][0]);c[1][1]++)
{
if (c[0][0]+c[0][1]+c[1][0]+c[1][1]>=n)
// this condition ensures that elements of the last row and
// column are positive and that every line and column has a
//total equals to n. It is the mathematical traduction that the
//last element of the matrix c[2][2] is non negative, that is that the sum of elements of the submatrix without last row an column is at least equal to (m-2)*n.
{
u=u+1;
}
}
}
}
}
}
cout<<"there exist "<<u<<"matrix with dimension 3 with positive elements and such that the total of every lign and every column equals"<<n;
return 0;
}
int max (intx,int y)
{
if (x<y) return y;
else return x;
}
second program : for m=4 :
#include <iostream.h>
int max(int,int);
int main()
{
unsigned long u; // counter of matrix of dimension 4 with the
// two properties
int n; // dimension
cout<<"m=4. Enter n, the dimension of the matrix :";
cin>>n;
int c[2][2]; // c denotes any matrix with dimension m=3
//property of the sum enables us to work with a
// reduced dimension (3 instead of 4)
for (c[0][0]=0; c[0][0]<=n; c[0][0]++)
{
for (c[0][1]=0; c[0][1]<=n-c[0][0]; c[0][1]++)
{
for (c[0][2]=0; c[0][2]<=n-c[0][0]-c[0][1]; c[0][2]++)
{
for (c[1][0]=0; c[1][0]<=n-c[0][0]; c[1][0]++)
{
for (c[2][0]=0; c[2][0]<=n-c[0][0]-c[1][0]; c[2][0]++)
{
for c[1][1]=0;c[1][1]<=n-max(c[0][1], c[1][0]);c[1][1]++)
{
for (c[2][1]=0; c[2][1]<=n-max(c[0][1]+c[1][1], c[1][0]);
c[2][1]++)
{
for (c[1][2]=0; c[1][2]<=n-max(c[1][0]+c[1][1],
c[0][1]); c[1][2]++)
{
for (c[2][2]=0; c[2][2]<=n-max(c[0][2]+c[1][2],
c[2][0]+c[2][1]); c[2][2]++)
{
if (c[0][0]+c[0][1]+c[0][2]+c[1][0]+c[1][1]+c[1][2]
+c[2][0]+c[2][1]+c[2][2]>=2*n)
// this condition ensures that elements o the last row and
// column are positive and that every line and column has a
//total equals to n. It is the mathematical traduction that the
//last element of the matrix c[3][3] is non negative, that is that the sum of elements of the submatrix without last row an column is at least equal to (m-2)*n.
{
u=u+1;
}
}
}
}
}
}
}
}
}
}
cout<<"there exist "<<u<<"matrix with dimension 4 with positive elements and such that the total of every lign and every column equals"<<n;
return 0;
}
int max (intx,int y)
{
if (x<y) return y;
else return x;
}
