Got Questions? Get Answers.
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:
how to avoid a double for loop

Subject: how to avoid a double for loop

From: gudny

Date: 9 Mar, 2010 15:41:38

Message: 1 of 7

Hello everyone,
I have a matrix A of 1 and 0's and I would like to know the indices of
any two columns that are either equal, or which are identical except
one column has zeros where the other has 1's and vice versa. (the
background is that these are cues for questions, and I would like if
there are identical questions, so that one of them is useless).
Now I do this with two for loops, going through all columns pairwise
and I would be very grateful if someone has an idea how this can be
done more effectively!

Here my loop:
for i = 1: m-1
        for j = i+1:m
            if isequal(A(:,i), A(:,j)) %are any two columns equal?
Then the first column index is to be removed from the list of
questions.
                 remove(i) = 1;
            else
                T = A(:,i)+A(:,j); % are any two columns mirror
images?
                if all(T == 1)
                    remove(i) = 1;
                end
            end
       end
    end
    questions = questions(~remove);

Subject: how to avoid a double for loop

From: Husam Aldahiyat

Date: 9 Mar, 2010 16:49:03

Message: 2 of 7

gudny <gudnyg@gmail.com> wrote in message <f06f2bf8-15c5-47df-b94e-883f7d7e8020@o3g2000yqb.googlegroups.com>...
> Hello everyone,
> I have a matrix A of 1 and 0's and I would like to know the indices of
> any two columns that are either equal, or which are identical except
> one column has zeros where the other has 1's and vice versa. (the
> background is that these are cues for questions, and I would like if
> there are identical questions, so that one of them is useless).
> Now I do this with two for loops, going through all columns pairwise
> and I would be very grateful if someone has an idea how this can be
> done more effectively!
>
> Here my loop:
> for i = 1: m-1
> for j = i+1:m
> if isequal(A(:,i), A(:,j)) %are any two columns equal?
> Then the first column index is to be removed from the list of
> questions.
> remove(i) = 1;
> else
> T = A(:,i)+A(:,j); % are any two columns mirror
> images?
> if all(T == 1)
> remove(i) = 1;
> end
> end
> end
> end
> questions = questions(~remove);

Try this:

% remove duplicate columns
o1 = transpose(unique(a','rows'));

% remove mirror images
o2 = ~o1;
[b,c,d] = unique([o1,~o1]','rows');
k = sort(d);
k2 = k(~diff(k));
s = k2(k2<=ceil(size(b,1)/2));

o1(:,s) = [];

I haven't tested it but should work.

Subject: how to avoid a double for loop

From: gudny

Date: 10 Mar, 2010 10:16:50

Message: 3 of 7

On Mar 9, 5:49 pm, "Husam Aldahiyat" <numand...@gmail.com> wrote:
> gudny <gud...@gmail.com> wrote in message <f06f2bf8-15c5-47df-b94e-883f7d7e8...@o3g2000yqb.googlegroups.com>...
> > Hello everyone,
> > I have a matrix A of 1 and 0's and I would like to know the indices of
> > any two columns that are either equal, or which are identical except
> > one column has zeros where the other has 1's and vice versa. (the
> > background is that these are cues for questions, and I would like if
> > there are identical questions, so that one of them is useless).
> > Now I do this with two for loops, going through all columns pairwise
> > and I would be very grateful if someone has an idea how this can be
> > done more effectively!
>
> > Here my loop:
> > for i = 1: m-1
> >         for j = i+1:m
> >             if isequal(A(:,i), A(:,j))   %are any two columns equal?
> > Then the first column index is to be removed from the list of
> > questions.
> >                  remove(i) = 1;
> >             else
> >                 T = A(:,i)+A(:,j); % are any two columns mirror
> > images?
> >                 if all(T == 1)
> >                     remove(i) = 1;
> >                 end
> >             end
> >        end
> >     end
> >     questions = questions(~remove);
>
> Try this:
>
> % remove duplicate columns
> o1 = transpose(unique(a','rows'));
>
> % remove mirror images
> o2 = ~o1;
> [b,c,d] = unique([o1,~o1]','rows');
> k = sort(d);
> k2 = k(~diff(k));
> s = k2(k2<=ceil(size(b,1)/2));
>
> o1(:,s) = [];
>
> I haven't tested it but should work.

Thank you, this is a nice solution. Now I am exited to see if my
program will become faster!

Subject: how to avoid a double for loop

From: gudny

Date: 11 Mar, 2010 10:22:17

Message: 4 of 7

On 10 Mrz., 11:16, gudny <gud...@gmail.com> wrote:
> On Mar 9, 5:49 pm, "Husam Aldahiyat" <numand...@gmail.com> wrote:
>
>
>
>
>
> >gudny<gud...@gmail.com> wrote in message <f06f2bf8-15c5-47df-b94e-883f7d7e8...@o3g2000yqb.googlegroups.com>...
> > > Hello everyone,
> > > I have a matrix A of 1 and 0's and I would like to know the indices of
> > > any two columns that are either equal, or which are identical except
> > > one column has zeros where the other has 1's and vice versa. (the
> > > background is that these are cues for questions, and I would like if
> > > there are identical questions, so that one of them is useless).
> > > Now I do this with two for loops, going through all columns pairwise
> > > and I would be very grateful if someone has an idea how this can be
> > > done more effectively!
>
> > > Here my loop:
> > > for i = 1: m-1
> > >         for j = i+1:m
> > >             if isequal(A(:,i), A(:,j))   %are any two columns equal?
> > > Then the first column index is to be removed from the list of
> > > questions.
> > >                  remove(i) = 1;
> > >             else
> > >                 T = A(:,i)+A(:,j); % are any two columns mirror
> > > images?
> > >                 if all(T == 1)
> > >                     remove(i) = 1;
> > >                 end
> > >             end
> > >        end
> > >     end
> > >     questions = questions(~remove);
>
> > Try this:
>
> > % remove duplicate columns
> > o1 = transpose(unique(a','rows'));
>
> > % remove mirror images
> > o2 = ~o1;
> > [b,c,d] = unique([o1,~o1]','rows');
> > k = sort(d);
> > k2 = k(~diff(k));
> > s = k2(k2<=ceil(size(b,1)/2));
>
> > o1(:,s) = [];
>
> > I haven't tested it but should work.
>
> Thank you, this is a nice solution. Now I am exited to see if my
> program will become faster!

I was a little bit to eager there, it turns out it doesn't work, as
the wrong questions get deleted. If there is only 1 set of mirror
questions, it is enough to change the last line:
1(:,s(m)) = [];
but if there are more than one pair of mirror questions, the false
ones might get deleted (that is both [1,0,0] and [0,1,1] might get
deleted, but the other pair [0,1,0] and [1,0,1] would not be deleted,
instead of one of each pair...)
all the information needed is in the output of unique, I am just
having a hard time figuring out how to do this.

Subject: how to avoid a double for loop

From: gudny

Date: 11 Mar, 2010 12:12:31

Message: 5 of 7

On 11 Mrz., 11:22, gudny <gud...@gmail.com> wrote:
> On 10 Mrz., 11:16,gudny<gud...@gmail.com> wrote:
>
>
>
>
>
> > On Mar 9, 5:49 pm, "Husam Aldahiyat" <numand...@gmail.com> wrote:
>
> > >gudny<gud...@gmail.com> wrote in message <f06f2bf8-15c5-47df-b94e-883f7d7e8...@o3g2000yqb.googlegroups.com>...
> > > > Hello everyone,
> > > > I have a matrix A of 1 and 0's and I would like to know the indices of
> > > > any two columns that are either equal, or which are identical except
> > > > one column has zeros where the other has 1's and vice versa. (the
> > > > background is that these are cues for questions, and I would like if
> > > > there are identical questions, so that one of them is useless).
> > > > Now I do this with two for loops, going through all columns pairwise
> > > > and I would be very grateful if someone has an idea how this can be
> > > > done more effectively!
>
> > > > Here my loop:
> > > > for i = 1: m-1
> > > >         for j = i+1:m
> > > >             if isequal(A(:,i), A(:,j))   %are any two columns equal?
> > > > Then the first column index is to be removed from the list of
> > > > questions.
> > > >                  remove(i) = 1;
> > > >             else
> > > >                 T = A(:,i)+A(:,j); % are any two columns mirror
> > > > images?
> > > >                 if all(T == 1)
> > > >                     remove(i) = 1;
> > > >                 end
> > > >             end
> > > >        end
> > > >     end
> > > >     questions = questions(~remove);
>
> > > Try this:
>
> > > % remove duplicate columns
> > > o1 = transpose(unique(a','rows'));
>
> > > % remove mirror images
> > > o2 = ~o1;
> > > [b,c,d] = unique([o1,~o1]','rows');
> > > k = sort(d);
> > > k2 = k(~diff(k));
> > > s = k2(k2<=ceil(size(b,1)/2));
>
> > > o1(:,s) = [];
>
> > > I haven't tested it but should work.
>
> > Thank you, this is a nice solution. Now I am exited to see if my
> > program will become faster!
>
> I was a little bit to eager there, it turns out it doesn't work, as
> the wrong questions get deleted. If there is only 1 set of mirror
> questions, it is enough to change the last line:
> 1(:,s(m)) = [];
> but if there are more than one pair of mirror questions, the false
> ones might get deleted (that is both [1,0,0] and [0,1,1] might get
> deleted, but the other pair [0,1,0] and [1,0,1] would not be deleted,
> instead of one of each pair...)
> all the information needed is in the output of unique, I am just
> having a hard time figuring out how to do this.

Ok, so I have one solution:
            b = b';
            [b,m,d] = unique([b,~b]', 'rows', 'first');%remove mirror
columns
            d = m(d);
            order = [1:length(d)]';
            d2 = order-d;
            index = find(d2>0);
            to_delete = min(index-length(d)/2, d(index));
            to_delete = unique(to_delete);
            questions(to_delete) = [];
I am guessing the stuff in the middle could be done more efficiently,
but it works!

Subject: how to avoid a double for loop

From: Roger Stafford

Date: 11 Mar, 2010 22:52:04

Message: 6 of 7

gudny <gudnyg@gmail.com> wrote in message <ad9f2a23-be16-42f6-9e74-2afcff9cd825@i25g2000yqm.googlegroups.com>...
> Ok, so I have one solution: .....

  You might try this. It uses only one call to 'unique'. The result is placed in B.

T = A.';
p = T(:,1)==1;
T(p,:) = 1-T(p,:); % Complement T rows that have 1 in first col.
[t,m,t] = unique(T,'rows'); % Reduce to unique T rows ('last')
B = A(:,sort(m)); % Reduce to corresponding cols. in A

Roger Stafford

Subject: how to avoid a double for loop

From: gudny

Date: 15 Mar, 2010 10:41:36

Message: 7 of 7

On 11 Mrz., 23:52, "Roger Stafford"
<ellieandrogerxy...@mindspring.com.invalid> wrote:
> gudny<gud...@gmail.com> wrote in message <ad9f2a23-be16-42f6-9e74-2afcff9cd...@i25g2000yqm.googlegroups.com>...
> > Ok, so I have one solution: .....
>
>   You might try this.  It uses only one call to 'unique'.  The result is placed in B.
>
> T = A.';
> p = T(:,1)==1;
> T(p,:) = 1-T(p,:);   % Complement T rows that have 1 in first col.
> [t,m,t] = unique(T,'rows');   % Reduce to unique T rows ('last')
> B = A(:,sort(m));   % Reduce to corresponding cols. in A
>
> Roger Stafford

Thank you, that is if course a lot simpler and faster!

Tags for this Thread

No tags are associated with 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