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

Simplifying a large nested for-loop

Asked by Yu on 15 Nov 2011

I am trying to simplify a nested for-loop. Any suggestions would be highly appreciated!

The structure of the problem in its crudest form is the follows:

comb=zeros(1,N);   %where N is a large number like 100
comb(1)=1;
for m2=1:N2    %where N2 is some predetermined number
  comb(2)=IX(m2,2);  %where IX is some pre-determined matrix
  if consistent(comb)  %where consistent(x) is a pre-specified fcn
      for m3=1:N3
          comb(3)=IX(m3,3);
          if consistent(comb)
              for m4=1:N4
                  comb(4)=IX(m4,4);
                  if consistent(comb)
                      ......  %this needs to be continued in exactly the same fashion until I reach the (N-1)th nested loop
                      for mN=1:NN
                         comb(N)=IX(mN,N);
                         if consistent(comb)
                             tot_dist=min(tot_dist(comb),tot_dist)  %where tot_dist(x) is a pre-specified fcn
                         else
                         end
                      end
                      ......
                  else
                  end
              end
          else
          end
      end
  else
  end
end  

The basic problem is conceptually the same as this: start from a vector comb=(1,0,...0). Select a number out of N2 numbers to fill the comb(2) if that selection satisfies some consistency condition. Do this for each of the remaining N-2 entries in comb, but the consistency condition is path dependent in the sense that your selection for comb(2) affects the consistency of a proposed selection for comb(3). Finally i need to select among all legitimate comb's the one that minimizes some total distance criterion.

Is there a way to handle this type of problems? Thank you very much in advance!

Yu

4 Comments

Yu on 15 Nov 2011

Naz, I agree... I wrote a small example with N=3 that illustrates the problem:

D=[1 3 -1;
0 1 2;
0 0 1];
A2=[1 2]; %A2 is just the list of rows with positive entries in the 2nd column of D.
A3=[2 3];
D_max=max(max(D));
comb=[1 0 0];
min_d=sum(sum(abs(D)));
best_comb=1:3;
a=2;
for m2=1:length(A2)
tot_d=0;
comb(2)=A2(m2);
if D(comb(2),2)>=0
tot_d=(m2~=length(A2))*D(comb(2),2)+(m2==length(A2))*a*D_max+tot_d;
for m3=1:length(A3)
comb(3)=A3(m3);
if D(comb(3),3)>=0
tot_d=(m3~=length(A3))*D(comb(3),3)+(m3==length(A3))*a*D_max+tot_d;
best_comb=comb*(tot_d<min_d)+best_comb*(tot_d>=min_d);
min_d=min(min_d,tot_d);
else
end
end
else
end
end

In this example: there are possibly 4 varieties of comb:
(1,1,2): this is not ruled out since D(1,3)<0
(1,1,3): this has a tot_d of 9
(1,2,2): this has a tot_d of 8
(1,2,3): this has a tot_d of 12
Hence the algorithm picks (1,2,2).

Is there any hope to extend the setting to N relatively large?

Thanks.

Yu on 15 Nov 2011

sorry i didn't know that the tab's got all lost after i pasted the code from Matlab to the commenting area.

Daniel on 15 Nov 2011

The comments section does not allow formatting. You could edit your question with this information.

Yu

Products

No products are associated with this question.

2 Answers

Answer by Daniel on 15 Nov 2011
Accepted answer

It sounds like a recursive problem to me.

What about something like

   function comb = looper(comb, IX, n, N)
     if n > length(comb)
        return;
     end
     for m = 1:N(n)
        comb(n)=IX(m,n);
        if consistent(comb)
          comb = looper(comb, IX, n+1, N);
        end
     end
   end

You could call it with something like:

N = [N1, N2, N3, ..., Nn];
comb = looper(0, IX, 1, N);
tot_dist = min(tot_dist(comb), tot_dist);

2 Comments

Yu on 16 Nov 2011

Hi Daniel,

thanks a lot for your suggestion! It really helps!!

I have worked out the code for the little example with N=3 according to your suggestion (please refer to the modified question above).

I'm working on the generalization of this to a large N, before officially declaring this question be resolved.

Thanks again!

Yu

Yu on 17 Nov 2011

So I have the version for a general value of N. This is very helpful. Thanks!

Daniel
Answer by Yu on 16 Nov 2011

The code for the small example incorporating Daniel's suggestion:

clear all
clc
global best_comb_d min_d result i
D=[1 3 -1;
  0 1 2;
  0 0 1];
IX=[1 1 2; 
  0 2 3];
N=[1 2 2];
% D=[1 -1 2;
%     0 1 3;
%     0 0 1];
% IX=[1 2 1;
%     0 0 2;
%     0 0 3];
% N=[1 1 3];
a=2;
min_d=a*sum(sum(abs(D)));
best_comb_d=[1:3 min_d];
n=2;
comb_d=[1 0 0 0];
%==============
%Check intermediate steps
i=1;
result=zeros(10,4);
%================
comb_d=looper(comb_d,IX,a,n,N,D);
function comb_d=looper(comb_d,IX,a,n,N,D)
global best_comb_d min_d result i
if n>length(comb_d)-1
  result(i,:)=comb_d;
  i=i+1;
  best_comb_d=comb_d*(comb_d(length(comb_d))<min_d)+best_comb_d*(comb_d(length(comb_d))>=min_d);
  min_d=min(min_d,comb_d(length(comb_d)));
  if comb_d(length(comb_d)-1)==IX(N(length(N)),length(IX(1,:)))
      comb_d(length(comb_d))=0;
  else
      comb_d(length(comb_d))=comb_d(length(comb_d))-D(comb_d(n-1),n-1);
  end
  return;
end
D_max=max(max(D));
for m=1:N(n)
  comb_d(n)=IX(m,n);
  if D(comb_d(comb_d(n)),n)>=0
      d=(m~=N(n))*D(comb_d(n),n)+(m==N(n))*a*D_max;
      comb_d(length(comb_d))=comb_d(length(comb_d))+d;
      comb_d=looper(comb_d,IX,a,n+1,N,D);
  end
end
end  

I hope this will extends well to cases with large N.

Yu

0 Comments

Yu

Contact us