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:
vertorize a loop

Subject: vertorize a loop

From: Gareth Lennox

Date: 2 Jun, 2011 20:43:04

Message: 1 of 8

Hey everyone,

I wonder if anyone has any ideas of how i could vertorize a loop. As an example, i have a column vector

x = [1;
       2;
       3;
       4;
       5]

And i would like to construct the 10 by 2 matrix

x1 = [1 2;
         1 3;
         1 4;
         1 5;
         2 3;
         2 4;
         2 5;
         3 4;
         3 5;
         4 5]

I have a loop that will do this. However, for large problems it takes forever. Any help would be greatly appreciated.

Thanks,

Gareth

Subject: vertorize a loop

From: Matt J

Date: 2 Jun, 2011 20:54:04

Message: 2 of 8

 nchoosek(1:5,2)

Subject: vertorize a loop

From: Gareth Lennox

Date: 2 Jun, 2011 21:13:04

Message: 3 of 8

"Matt J" wrote in message <is8t9c$oml$1@newscl01ah.mathworks.com>...
> nchoosek(1:5,2)

Thanks, Matt. Yes, that would solve the example i gave. However, i'm looking to avoid enumerating all solutions. Maybe a more pertinent example would be,

x = [1;
       3;
       5]

To become

x1 = [1 2;
         1 3;
         1 4;
         1 5;
         1 6;
         3 4;
         3 5;
         3 6;
         5 6];

Then, some of those would be knocked out. For example, i could be left with

x1 = [1 4
         3 4
         3 5]

and then the code would produce

x2 = [1 4 5;
         1 4 6;
         3 4 5;
         3 4 6;
         3 5 6]
  
Basically, for each iteration, the feasible solutions would be extended to produce all solutions with one more variable.

Cheers

Subject: vertorize a loop

From: Roger Stafford

Date: 2 Jun, 2011 23:54:04

Message: 4 of 8

"Gareth Lennox" <celtlen@yahoo.co.uk> wrote in message <is8ud0$ruu$1@newscl01ah.mathworks.com>...
> Basically, for each iteration, the feasible solutions would be extended to produce all solutions with one more variable.
- - - - - - - -
  I think you still have some explaining to do, Gareth. In your first example, 5 occurred at the end of the 'x' list and was apparently used as a limit in the second column of x1, whereas in the second example 5 again was at the end of the x list but in the second column of x1 the limit used was 6. What is the logic involved? I can think of many possibilities but we shouldn't have to guess about such things. Perhaps the best thing you can do is to give us the "loop" you mentioned so as to hopefully answer all such questions.

Roger Stafford

Subject: vertorize a loop

From: Matt J

Date: 2 Jun, 2011 23:56:04

Message: 5 of 8

"Gareth Lennox" <celtlen@yahoo.co.uk> wrote in message <is8ud0$ruu$1@newscl01ah.mathworks.com>...
>
> x1 = [1 4
> 3 4
> 3 5]
>
> and then the code would produce
>
> x2 = [1 4 5;
> 1 4 6;
> 3 4 5;
> 3 4 6;
> 3 5 6]
>
> Basically, for each iteration, the feasible solutions would be extended to produce all solutions with one more variable.
======================

It's not clear from your example what range of values the appended variable is supposed to be able to take on, but for the above transition from x1 to x2, the following would work:

 [J,I]=ndgrid(5:6, 1:length(x1));
 x2=[x1(I(:),:), J(:)];
x2=x2(x2(:,end-1)<x2(:,end),:)

Subject: vertorize a loop

From: Gareth Lennox

Date: 3 Jun, 2011 00:21:04

Message: 6 of 8

"Roger Stafford" wrote in message <is97qs$lt9$1@newscl01ah.mathworks.com>...
> "Gareth Lennox" <celtlen@yahoo.co.uk> wrote in message <is8ud0$ruu$1@newscl01ah.mathworks.com>...
> > Basically, for each iteration, the feasible solutions would be extended to produce all solutions with one more variable.
> - - - - - - - -
> I think you still have some explaining to do, Gareth. In your first example, 5 occurred at the end of the 'x' list and was apparently used as a limit in the second column of x1, whereas in the second example 5 again was at the end of the x list but in the second column of x1 the limit used was 6. What is the logic involved? I can think of many possibilities but we shouldn't have to guess about such things. Perhaps the best thing you can do is to give us the "loop" you mentioned so as to hopefully answer all such questions.
>
> Roger Stafford

Ok, i'll start from the beginning. I need to emumerate solutions in a branch and bound algorithm. I have a list of sites labelled 1:n and solutions are combinations of sites. At each "branch" of the tree solutions are removed in they are inferior or infeasible and no further enumeration with thosesolution is carried forward.

So say after the first iteration, i'm left with the sites s = [1 5 7 9] when i started with sites 1:10. For the second iteration, i need all possible combinations with two sites where one of the sites in s is the first element. The loop which gives me this is (and i'll use the example with s = [1 5 7 9])

possible = [1 5 7 9]';
iter = 2;

newpossible = [];
for i = 1:size(possible,1)
    for j = possible(i,iter-1)+1:nsites
newpossible(end+1,1:iter) = [possible(i,1:iter-1) j];
end
end

This produces

 newpossible =

     1 2
     1 3
     1 4
     1 5
     1 6
     1 7
     1 8
     1 9
     1 10
     5 6
     5 7
     5 8
     5 9
     5 10
     7 8
     7 9
     7 10
     9 10

And it is this loop that i'd like to vectorize.

Apologies for my lack of clarity earlier :D

Gareth

Subject: vertorize a loop

From: Roger Stafford

Date: 3 Jun, 2011 05:21:04

Message: 7 of 8

"Gareth Lennox" <celtlen@yahoo.co.uk> wrote in message <is99dg$pmr$1@newscl01ah.mathworks.com>...
> newpossible = [];
> for i = 1:size(possible,1)
> for j = possible(i,iter-1)+1:nsites
> newpossible(end+1,1:iter) = [possible(i,1:iter-1) j];
> end
> end
> And it is this loop that i'd like to vectorize.
- - - - - - - - - -
  Your for-loop code wouldn't work for me unless 'iter' is equal to one greater than the number of columns in 'possible', which is the case in all the examples you have shown, so I have written it to be just that:

 iter = size(possible,2)+1;
 v = nsites-possible(:,iter-1);
 s = cumsum([1;v]);
 sz = s(end)-1;
 s = s(1:end-1);
 t = accumarray(s,-v,[sz,1]) + 1;
 t(1) = t(1) + nsites;
 newpossible = zeros(sz,iter);
 newpossible(:,iter) = cumsum(t);
 t = accumarray(s,1,[sz,1]);
 newpossible(:,1:iter-1) = possible(cumsum(t),:);

  This vectorized version looks more complicated than your for-loop solution. I had trouble working it out and there may be easier methods. It is possible that if you allocate space for 'newpossible' in advance using only the 'sz' computation above, your for-loop solution might then be faster than this code. Adding elements to 'newpossible' one at a time starting with an empty array as you do can slow down computation in a dramatic way for large arrays.

Roger Stafford

Subject: vertorize a loop

From: Gareth Lennox

Date: 3 Jun, 2011 12:08:04

Message: 8 of 8

> Your for-loop code wouldn't work for me unless 'iter' is equal to one greater than the number of columns in 'possible', which is the case in all the examples you have shown, so I have written it to be just that:
>
> iter = size(possible,2)+1;
> v = nsites-possible(:,iter-1);
> s = cumsum([1;v]);
> sz = s(end)-1;
> s = s(1:end-1);
> t = accumarray(s,-v,[sz,1]) + 1;
> t(1) = t(1) + nsites;
> newpossible = zeros(sz,iter);
> newpossible(:,iter) = cumsum(t);
> t = accumarray(s,1,[sz,1]);
> newpossible(:,1:iter-1) = possible(cumsum(t),:);
>
> This vectorized version looks more complicated than your for-loop solution. I had trouble working it out and there may be easier methods. It is possible that if you allocate space for 'newpossible' in advance using only the 'sz' computation above, your for-loop solution might then be faster than this code. Adding elements to 'newpossible' one at a time starting with an empty array as you do can slow down computation in a dramatic way for large arrays.
>
> Roger Stafford

Thanks very much, Roger. Your solutions speeds up the code markedly!!

Cheers,

Gareth

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