## Simplifying a large nested for-loop

on 15 Nov 2011

### Daniel (view profile)

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

Yu

### Yu (view profile)

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

### Yu (view profile)

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

### Daniel (view profile)

on 15 Nov 2011

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

## Products

No products are associated with this question.

### Daniel (view profile)

on 15 Nov 2011

It sounds like a recursive problem to me.

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

### Yu (view profile)

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

### Yu (view profile)

on 17 Nov 2011

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

### Yu (view profile)

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