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

*No products are associated with this question.*

Answer by Daniel Shub
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);

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!

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

Related Content

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

Learn moreOpportunities for recent engineering grads.

Apply Today
## 4 Comments

## Naz (view profile)

Direct link to this comment:http://www.mathworks.com/matlabcentral/answers/21239#comment_46175

The algorithm is just terrible. May be there is another way of doing it instead of loops? Do you have a general equation for it?

## Yu (view profile)

Direct link to this comment:http://www.mathworks.com/matlabcentral/answers/21239#comment_46196

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 (view profile)

Direct link to this comment:http://www.mathworks.com/matlabcentral/answers/21239#comment_46198

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

## Daniel Shub (view profile)

Direct link to this comment:http://www.mathworks.com/matlabcentral/answers/21239#comment_46206

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