Say we have a matrix of zeros and ones

0 1 1 1 0 0 0

1 1 1 1 0 1 1

0 0 1 0 0 1 0

0 1 1 0 1 1 1

0 0 0 0 0 0 1

0 0 0 0 0 0 1

and we want to find all the submatrices (we just need the row indices and column indices of the corners) with these properties:

- contain at least L ones and L zeros
- contain max H elements

i.e. take the previous matrix with L=1 and H=5, the submatrix 1 2 1 4 (row indices 1 2 and column indices 1 4)

satisfies the property 1 but has 8 elements (bigger than 5) so it is not good;

the matrix 4 5 1 2

is good because satisfies both the properties.

The objective is then to find all the submatrices with min area 2*L, max area H and containg at least L ones and L zeros.

If we consider a matrix as a rectangle it is easy to find all the possibile subrectangles with max area H and min area 2*L by looking at the divisors of all the numbers from H to 2*L.

For example, with H=5 and L=1 all the possibile subrectangles/submatrices are given by the divisors of

- H=5 -> divisors [1 5] -> possibile rectangles of area 5 are 1x5 and 5x1
- 4 -> divisors [1 2 4] -> possibile rectangles of area 4 are 1x4 4x1 and 2x2
- 3 -> divisors [1 3] -> possibile rectangles of area 3 are 3x1 and 1x3
- 2*L=2 -> divisors [1 2] -> possibile rectangles of area 2 are 2x1 and 1x2

I wrote this code, which, for each number finds its divisors and cycles over them to find the submatrices. To find the submatrices it does this: take for example a 1x5 submatrix, what the code does is to fix the first line of the matrix and move step by step (along all the columns of the matrix) the submatrix from the left edge of the matrix to the right edge of the matrix, then the code fixes the second row of the matrix and moves the submatrix along all the columns from left to right, and so on until it arrives at the last row.

It does this for all the 1x5 submatrices, then it considers the 5x1 submatrices, then the 1x4, then the 4x1, then the 2x2, etc.

The code do the job in 2 seconds (it finds all the submatrices) but for big matrices, i.e. 200x200, a lot of minutes are needed to find all the submatrices. So I wonder if there are more efficient ways to do the job, and eventually which is the most efficient.

This is my code:

clc;clear all;close all

P= [0 1 1 1 0 0 0 ;

1 1 1 1 0 1 1 ;

0 0 1 0 0 1 0 ;

0 1 1 0 1 1 1 ;

0 0 0 0 0 0 1 ;

0 0 0 0 0 0 1];

L=1;

H=5;

[R,C]=size(P);

sub=zeros(1,6);

counter=1;

tic

for sH = H:-1:2*L

div_sH=divisors(sH);

disp(['_______AREA ', num2str(sH), '_______'])

for i = 1:round(length(div_sH)/2)

div_small=div_sH(i);

div_big=div_sH(end-i+1);

if div_small <= R && div_big <= C

for j = 1:R-div_small+1

for k = 1:C-div_big+1

no_of_ones=length(find(P(j:j-1+div_small,k:k-1+div_big)));

if no_of_ones >= L && no_of_ones <= sH-L

sub(counter,:)=[j,j-1+div_small , k,k-1+div_big , div_small*div_big , counter];

counter=counter+1;

end

end

end

disp([' [', num2str(div_small), 'x', num2str(div_big), '] submatrices: ', num2str(size(sub,1))])

end

if div_small~=div_big

if div_small <= C && div_big <= R

for j = 1:C-div_small+1

for k = 1:R-div_big+1

no_of_ones=length(find(P(k:k-1+div_big,j:j-1+div_small)));

if no_of_ones >= L && no_of_ones <= sH-L

sub(counter,:)=[k,k-1+div_big,j,j-1+div_small , div_big*div_small, counter];

counter=counter+1;

end

end

end

disp([' [', num2str(div_big), 'x', num2str(div_small), '] submatrices: ', num2str(size(sub,1))])

end

end

end

end

fprintf('\ntime: %2.2fs\n\n',toc)

## 2 Comments

## Direct link to this comment

https://in.mathworks.com/matlabcentral/answers/395258-most-efficent-way-of-finding-submatrices-of-a-matrix#comment_932738

⋮## Direct link to this comment

https://in.mathworks.com/matlabcentral/answers/395258-most-efficent-way-of-finding-submatrices-of-a-matrix#comment_932738

## Direct link to this comment

https://in.mathworks.com/matlabcentral/answers/395258-most-efficent-way-of-finding-submatrices-of-a-matrix#comment_933113

⋮## Direct link to this comment

https://in.mathworks.com/matlabcentral/answers/395258-most-efficent-way-of-finding-submatrices-of-a-matrix#comment_933113

Sign in to comment.