Partitioning a 2D matrix
Partitioning a 2D matrix
Consider the following 2D matrix:
0,0,0,0,0
0,0,1,0,0
0,0,0,1,0
0,0,0,0,0
I could do only horizontal or vertical cuts stretching from end to end edges.
What could be the algorithm to use so I could find out how many times I can divide the matrix in 2 parts such that each of the 2 parts get equal number of cells with 1?
1 Answer
1
I assume you can do only one horizontal cut or vertical cut.
One approach for "one single matrix" is: ( You need to repetitively apply this to each partition you get ).
compute number of ones in each row and number of ones in each column, store them in two arrays like
OnesInRow[num_rows] , OnesInColumn[num_cols]
Also compute the total number of 1s in the matrix which is actually sum of values of all elements in either of the above arrays.
total = Sum( All elements in OnesInRow )
For example, you can get the number of ones in row number 2 like OnesInRow[1] ( assuming row index starts from 0 ). Similarly number of ones in col number 3 is OnesInCol[2].
OnesInRow[1]
OnesInCol[2]
Now consider a horizontal cut like this:
0,0,0,0,0
0,0,1,0,0
0,0,0,1,0
0,0,0,0,0
The number of ones that you get in each partition is : OnesInRow[0], Total - OnesInRow[0]
OnesInRow[0], Total - OnesInRow[0]
For this:
0,0,0,0,0
0,0,1,0,0
0,0,0,1,0
0,0,0,0,0
it is: Total - ( OnesInRow[0] + OnesInRow[1] ) , OnesInRow[0] + OnesInRow[1]
Total - ( OnesInRow[0] + OnesInRow[1] ) , OnesInRow[0] + OnesInRow[1]
For this:
0,0, | 0,0,0
0,0, | 1,0,0
0,0, | 0,1,0
0,0, | 0,0,0
it is: Total - (OnesInCol[0] + OnesInCol[1] ), OnesInCol[0] + OnesInCol[1]
Total - (OnesInCol[0] + OnesInCol[1] ), OnesInCol[0] + OnesInCol[1]
So you just need to consider all row cuts and col cuts and take which of those cuts will lead to two equal partitions of ones.
int count = 0;
int prevOnes = 0;
int onesInRowAboveThisCut = 0;
for ( int i = 1; i < rows; i++ )
onesInRowAboveThisCut = prevOnes + OnesInRow[i-1];
if ( onesInRowAboveThisCut= total/2 ) count++;
prevOnes = onesInRowAboveThisCut;
prevOnes = 0;
int onesInColBeforeThisCut = 0;
for ( int i = 1; i < cols; i++ )
onesInColBeforeThisCut = prevOnes + OnesInCol[i-1];
if ( onesInColBeforeThisCut = total/2 ) count++;
prevOnes = onesInColBeforeThisCut ;
return count;
Then for each matrix you get from such a partition you could repeat the process recursively, until you cant cut i.e. there is only one element in the array.
At each recursion you maintain a count variable and update it.
By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.
