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
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

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

Opportunities for recent engineering grads.

## 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 (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.