Simplifying a large nested for-loop

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

[Naz]

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]

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]

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]

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

Answer 1

[Daniel Shub]

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]

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]

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

Answer 2

[Yu]

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