Program to fill a matrix with 1s and 0s to such that it satisfies the given row and column sums

Question

I am supposed to write a program which fills a matrix (flag[][], here) with 0s and 1s such that the the given row and column sums are satisfied. The row and column sums are to be calculated by adding the fractional part of the elements of a[][]. I wrote the code given below, which works when I run just this part of it:

#include<stdio.h>
#include<stdlib.h>
    
int main()
{int m=3;
 int flag[3][3];
 int rSum[] = {1,1,2};
 int cSum[] = {2,1,1};
for(int i=0;i<m;i++)
{int k = 0;
    for(int j=0;j<rSum[i];j++)
    {
        if(cSum[k] == 0)
        {
            j--;
            k++;
        }
        else
        {  
            flag[i][k] = 1;
            cSum[k]--;
            k++;
        }
    }
}
return 0;
}

But the whole code gives wrong output on running. The whole code:

 #include<stdio.h>
 #include<stdlib.h>

 int main()
{
printf("Enter the size of matrix: ");
int m,n;
scanf("%d %d",&m,&n);
float a[m][n];

printf("Enter the elements: ");
for(int i=0;i<m;i++)
{
    for(int j=0;j<n;j++)
    {
        scanf("%f",&a[i][j]);
    }
}

float b[m][n];
for(int i=0;i<m;i++)
{
    for(int j=0;j<n;j++)
    {
        b[i][j] = a[i][j] - (int)a[i][j];
        printf("%f ",b[i][j]);  
    }
    printf("\n");
}
printf("\n\n\n");
float rSum[m], cSum[n];
for(int i=0;i<n;i++)
{
    cSum[i] = 0;
}
for(int i=0;i<m;i++)
{
    rSum[i] = 0;
}

for(int i=0;i<m;i++)
{
    for(int j=0;j<n;j++)
    {
        rSum[i] += b[i][j];
    }

}

for(int i=0;i<n;i++)
{
    for(int j=0;j<m;j++)
    {
        cSum[i] += b[j][i];
    }

}
printf("\nrSum:");
for(int i=0;i<m;i++)
{
    printf("%f ",rSum[i]);
}
printf("\ncSum:");
for(int i=0;i<n;i++)
{
    printf("%f ",cSum[i]);
}
    
int flag[m][n];

for(int i=0;i<m;i++)
{
    for(int j=0;j<n;j++)
    {
        flag[i][j] = 0;
    }
}

for(int i=0;i<m;i++)
{int k = 0;
    for(int j=0;j<rSum[i];j++)
    {
        if(cSum[k] == 0)
        {
            
            j--;
            k++;
        }
        else
        {    
            flag[i][k] = 1;
            cSum[k]--;
            k++;
        }
    }
}   
printf("\n\n\n");
for(int i=0;i<n;i++)
{
    for(int j=0;j<m;j++)
    {
        printf("%d ",flag[i][j]);
    }
    printf("\n");
}
return 0;
}

Can anyone please point out the mistake I am making? Why is the first code working fine, but not the second one? Also, my input for a[][] was {1.2 , 3.4, 2.4, 3.9, 4.0, 2.1, 7.9, 5.6, 0.5}.

Answer 1

In your program, you have one big mistake that is repeatedly made in many parts: Do not behave float type variables as if they are int.

First of all, you shouldn't compare (==) a float number with any number. So cSum[k] == 0 is wrong. Instead, you should specify a threshold and compare distance between the number and the threshold.

So change this line

if(cSum[k] == 0)

with

if (fabsf(cSum[k]) < epsilon) // You can set epsilon to 0.0005

where epsilon is a very small number (that is float type) that can be used as threshold.

Also, cSum[k] -= 1.0f; is much better than cSum[k]--; It is not necessarily wrong but you should tell cSum[k] is a float number to a person who reads your code.

Lastly, change this line

for(int j=0;j<rSum[i];j++)

with

for(int j=0;j<round(rSum[i]);j++)

I'll give you an example. Suppose

j = 2  rSum[i] = 2.00000000000000009

What can you say about j < rSum[i]?

In fact, we want them to be equal to each other but due to the precision issue in floating numbers they are not equal. Checking j < rSum[i] concludes that rSum[i] is greater than j. But it is wrong. So we should force them to be equal. For this reason, you can use round function to prevent this situation. You will get

j = 2  rSum[i] = 2.00000000000000000

You can find further information here.

In brief, in your program, since the comparison did not succeed, required if and for sections are passed.

Only change this part and add (#include <math.h>):

float epsilon = 0.0005f;
for(int i=0;i<m;i++)
{int k = 0;
    for(int j=0;j<round(rSum[i]);j++)
    {
        if(fabsf(cSum[k]) <epsilon)
        {
            j--;
            k++;
        }
        else
        {
            flag[i][k] = 1;
            cSum[k] -= 1.0f;
            k++;
        }
    }
}

After, you will find the output as you expected:

1 0 0 
1 0 0
0 1 1

Answer 2

The problems

First off, I don't see where you are setting your matrix to 0. If you are already receiving a matrix where every number is 0, please specify so.

But I also think that your logic in general can't resolve the given problem. You are using a greedy strategy that puts a number, whenever it is currently possible. But you have no guarantee that this is correct for the final solution.

Example

Let's say you have the following matrix:

1 0 0 - 1  
0 0 1 - 1  
1 0 1 - 2  
| | |  
2 0 2

As you can see, the sums of rows are {1, 1, 2} and the sums of columns are {2, 0, 2}. Now your algorithm is going to correctly place the 1 in flag[0][0] then, as the row is completed, it is going to move to the next row.
Here it is going to place a 1 in the first column (flag[1][0]), as the column sum still allows for it and so does the row sum. Now again we move to the next row, having completed the second sum of rows.
The first column is already full, so we leave it with 0. The next column can't have anything but 0s, as its sum is 0. So we are only left with the 3rd column, where we put a 1. But now our final matrix flag looks like this:

1 0 0  
1 0 0  
0 0 1  

Which is clearly a wrong answer.

Possible solution

I would recommend trying to solve this problem using backtracking.