Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Thread Subject:
quick search of a binary array within a binary matrix.

Subject: quick search of a binary array within a binary matrix.

From: Jon

Date: 30 May, 2011 18:51:02

Message: 1 of 10

Dear all
My question is:
I have a binary matrix
B = [1 0 0, 0 1 1, 0 0 1, 1 1 0];
Besides, I have a binary vecor
b = [1 0 1]
Is there any efficient way to check if b is contained in B? is it an advantage to have only binary numbers? And the fact that I dont want to know the exact position but only if it is contained? can be done by indexing?

In the real case, b is made up by 3000 elements so indexing may not be possible.

Thank you very much in advance.

Subject: quick search of a binary array within a binary matrix.

From: dm

Date: 30 May, 2011 19:19:07

Message: 2 of 10

"Jon" wrote in message <is0oum$e82$1@newscl01ah.mathworks.com>...
> Dear all
> My question is:
> I have a binary matrix
> B = [1 0 0, 0 1 1, 0 0 1, 1 1 0];
> Besides, I have a binary vecor
> b = [1 0 1]
> Is there any efficient way to check if b is contained in B? is it an advantage to have only binary numbers? And the fact that I dont want to know the exact position but only if it is contained? can be done by indexing?
>
> In the real case, b is made up by 3000 elements so indexing may not be possible.
>
> Thank you very much in advance.

Probably not the most compact solution, but works:

B = [1 0 0; 0 1 1; 0 0 1; 1 1 0; 1 0 1];
b = [1 0 1];
[M N] = size(B);
C = repmat(b,M,1)
t = sum(~xor(B,C),2);
if ~isempty(find(t==numel(b), 1))
    isMem = 1
end

Subject: quick search of a binary array within a binary matrix.

From: ImageAnalyst

Date: 30 May, 2011 19:40:23

Message: 3 of 10

Did you look at bwhitmiss() in the Image Processing Toolbox?

Or else try this:
http://www.mathworks.com/matlabcentral/fileexchange/23998-findsubmat

Subject: quick search of a binary array within a binary matrix.

From: Jon

Date: 30 May, 2011 20:27:04

Message: 4 of 10

Thank you very much for your rapid response!

There is not any special function to do that? I mean, doing
tmp=find(b*B'==sum(b));
is usually faster, rigth?

Thank you again!

Subject: quick search of a binary array within a binary matrix.

From: ImageAnalyst

Date: 30 May, 2011 21:13:55

Message: 5 of 10

How much speed do you need? Do you really think you'll notice any
time difference for such tiny arrays of 3000 elements or less?

Subject: quick search of a binary array within a binary matrix.

From: ImageAnalyst

Date: 30 May, 2011 22:27:52

Message: 6 of 10

You had a slight error in your definition of B - commas instead of
semicolons. I also changed b so that there was a match.
Corrected version:

B = [1 0 0; 0 1 1; 0 0 1; 1 1 0]
b = [1 1 0]
matchingRow = find(b*B' == sum(b))

That works fine, so if you want that, that's fine, and it doesn't
require any toolbox functions.

Subject: quick search of a binary array within a binary matrix.

From: Roger Stafford

Date: 30 May, 2011 22:38:02

Message: 7 of 10

"Jon" wrote in message <is0oum$e82$1@newscl01ah.mathworks.com>...
> Dear all
> My question is:
> I have a binary matrix
> B = [1 0 0, 0 1 1, 0 0 1, 1 1 0];
> Besides, I have a binary vecor
> b = [1 0 1]
> Is there any efficient way to check if b is contained in B? is it an advantage to have only binary numbers? And the fact that I dont want to know the exact position but only if it is contained? can be done by indexing?
>
> In the real case, b is made up by 3000 elements so indexing may not be possible.
>
> Thank you very much in advance.

"Jon" wrote in message <is0uio$r70$1@newscl01ah.mathworks.com>...
> Thank you very much for your rapid response!
>
> There is not any special function to do that? I mean, doing
> tmp=find(b*B'==sum(b));
> is usually faster, rigth?
>
> Thank you again!
- - - - - - - - -
  It is not clear what you are asking where you write

B = [1 0 0, 0 1 1, 0 0 1, 1 1 0];

You called it a matrix but, as it stands, it is a 1 by 12 vector. If this is really what you mean, then are you asking whether b = [1 0 1] is one of the ten vectors within B: [1 0 0], [0 0 0], [0 0 1], [0 1 1], [1 1 0], [1 0 0], [0 0 1], [0 1 1], [1 1 1], [1 1 0], or are you asking whether b is one of the four vectors [1 0 0], [0 1 1, [0 0 1], [1 1 0]?

  If the latter is what you mean, then turn B into an actual matrix:

B = [1 0 0; 0 1 1; 0 0 1; 1 1 0];

and use 'ismember' with the 'rows' option:

 t = any(ismember(b,B,'rows'));

  If it is the former meaning then you should use the 'hankel' function on the vector version of B before using 'ismember'.

  One thing is certain. The code

tmp=find(b*B'==sum(b));

will not get the answer you seem to be asking for by an conceivable stretch of the imagination.

Roger Stafford

Subject: quick search of a binary array within a binary matrix.

From: Roger Stafford

Date: 31 May, 2011 01:40:05

Message: 8 of 10

"Roger Stafford" wrote in message <is168a$fk2$1@newscl01ah.mathworks.com>...
> ..........
> One thing is certain. The code
>
> tmp=find(b*B'==sum(b));
>
> will not get the answer you seem to be asking for by an conceivable stretch of the imagination.
>
> Roger Stafford
- - - - - - - - -
  It has occurred to me that by "b is contained in B" you might have meant that at least one of the rows of B (after being converted to a matrix) has the property that each of its binary bits is a 1 wherever the corresponding b vector has a 1 - that is, that a 1 denotes membership in the set of possible columns indices - rather than that the two rows are bit-for-bit equal. If the former was your meaning of 'contained in', then the matrix multiplication you mentioned would indeed work properly.

  My comment about that is twofold. I think you should have used a better way of wording your problem than just "contained in", and I needed a greater "stretch of the imagination".

Roger Stafford

Subject: quick search of a binary array within a binary matrix.

From: Steven_Lord

Date: 31 May, 2011 13:40:44

Message: 9 of 10



"Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid> wrote in
message news:is1gtl$ao4$1@newscl01ah.mathworks.com...
> "Roger Stafford" wrote in message
> <is168a$fk2$1@newscl01ah.mathworks.com>...
>> ..........
>> One thing is certain. The code
>>
>> tmp=find(b*B'==sum(b));
>>
>> will not get the answer you seem to be asking for by an conceivable
>> stretch of the imagination.
>>
>> Roger Stafford
> - - - - - - - - -
> It has occurred to me that by "b is contained in B" you might have meant
> that at least one of the rows of B (after being converted to a matrix) has
> the property that each of its binary bits is a 1 wherever the
> corresponding b vector has a 1 - that is, that a 1 denotes membership in
> the set of possible columns indices - rather than that the two rows are
> bit-for-bit equal. If the former was your meaning of 'contained in', then
> the matrix multiplication you mentioned would indeed work properly.

If that's the meaning the OP intended, they can look at the ISMEMBER
function with the 'rows' flag.

--
Steve Lord
slord@mathworks.com
To contact Technical Support use the Contact Us link on
http://www.mathworks.com

Subject: quick search of a binary array within a binary matrix.

From: Roger Stafford

Date: 31 May, 2011 17:04:04

Message: 10 of 10

"Steven_Lord" <slord@mathworks.com> wrote in message <is2r4s$nov$1@newscl01ah.mathworks.com>...
> If that's the meaning the OP intended, they can look at the ISMEMBER
> function with the 'rows' flag.
- - - - - - - - - -
  Steve, I don't think 'ismember' with 'rows' option would be appropriate with that meaning of "contained in" when the solution

 any(b*B'==sum(b))

is so much more efficient. As I pointed out earlier in this thread, 'ismember' should be used with the other meaning.

Roger Stafford

Tags for this Thread

What are tags?

A tag is like a keyword or category label associated with each thread. Tags make it easier for you to find threads of interest.

Anyone can tag a thread. Tags are public and visible to everyone.

Contact us