Pattern search in a matrix

[dsv]

I have an NxN matrix, say, A[N][N] where N could be over 100. The
elements of A are either zeros or ones. I want to find whether there
are at least W columns having at least H zeros each in the same rows.

e.g., when N=5, W=3 and H=2, the matrix

0 1 0 0 1
1 0 1 0 1
0 1 1 0 0
1 0 0 1 0
0 1 1 0 0

has the required pattern. The 1st, 4th and 5th columns of the 3rd and
5th rows are 0.

Can someone suggest an efficient algorithm for searching for this
pattern? What I have in mind is like a factorial search, so it is
quite expensive. Here is its outline.

1. Scan all columns and count the number of zeros in each column. If
the number of columns with at least H zeros is less than W, then the
required pattern is missing.

for (j=0, nz=0; j<N; j++) {
for (i=0, cz[j]=0; i<N; i++)
if (A[j]==0) cz[j]++;
if (cz[j] >= H) nz++;
}
if (nz<W) return FALSE;

2. Take the column jmin with the minimum number of zeros G > H. H
zeros can be picked in <G choose H> ways. For each of the ways, check
the other columns for zeros in the same H rows. If there are W such
columns, then the pattern is found.

3. If not, go to the column jmin2 with the second-lowest number of
zeros G2 > H. As before, H zeros can be picked in <G2 choose H> ways.
For each of these ways, look for W-1 zeros in the same rows in columns
other than jmin and jmin2. If they exist, then the pattern is found.

4. Otherwise keep doing this for N-W columns. If no success, then the
pattern does not exist.

This algorithm should work, I think, but not very efficiently,
especially for large N. Any suggestions for a better one?

dsv

 

[Eric Sosman]

I have an NxN matrix, [...]

Can someone suggest an efficient algorithm[...]

Try comp.programming for advice on algorithms. If you then
have questions about implementing the chosen method, choose your
implementation language (C, C++, Algol, ...) and ask in *one* forum.

 

[Victor Bazarov]

I have an NxN matrix, say, A[N][N] where N could be over 100. The
elements of A are either zeros or ones. I want to find whether there
are at least W columns having at least H zeros each in the same rows.

e.g., when N=5, W=3 and H=2, the matrix

0 1 0 0 1
1 0 1 0 1
0 1 1 0 0
1 0 0 1 0
0 1 1 0 0

has the required pattern. The 1st, 4th and 5th columns of the 3rd and
5th rows are 0.

Can someone suggest an efficient algorithm for searching for this
pattern?

You're in a wrong newsgroup. Please consider posting to
comp.programming when you need an algorithm. Here we talk C++ language
issues.

Which volume of TAOCP is "Sorting and Searching"? Third? Consider
getting yourself a copy.

Also, read the FAQ, especially section 5.

> [..]

V