MATLAB: Generating possible sets that do not violate some condition

combinationsconditionalsubsets

I need to generate subsets that do not violate the precedence relationships. I have tasks numbered from 1 to 10. For example, task 4 cannot be done without doing task 1 and 2. I wrote a function to generate those sets for inputs of tasks, precedence matrix, and size of the subset(n):
 function [ e ] = subsets( tasks, pre, n )
 poss = combntns(tasks, n)
 [r c] = size(poss);
 e = zeros(size(poss));
 for i = 1:r
     for j = 1:n
         if(any(pre(poss(i,j),:))~=0)
             vec = find(pre(poss(i,j),:))
             if(ismember(poss(i,:), vec)==length(vec))
                 e(i,j) = 1;
             end
         end
     end
 end
 end
There is a problem up to now. If I resolve it, I will use the "e" matrix to write the valid subsets to another variable.
You can consider pre matrix as something like below:
 pre =
      0     0     0     0     0     0     0     0     0     0
      1     0     0     0     0     0     0     0     0     0
      0     0     0     0     0     0     0     0     0     0
      0     0     1     0     0     0     0     0     0     0
      1     0     1     1     0     0     0     0     0     0
      1     0     1     1     1     0     0     0     0     0
      0     1     0     0     0     0     0     0     0     0
      1     1     1     1     1     1     1     0     0     0
      1     1     1     1     1     1     1     1     0     0
      1     1     1     1     1     1     1     1     1     0
Thanks for your help in advance.

Best Answer

It looks as though in the line
 if(ismember(poss(i,:), vec)==length(vec))
you meant that if the number of true values in "ismember(poss(i,:), vec)" is equal to the length of 'vec', then you would set e(i,j) to 1. However I don't think that is what it achieves. You would have to have
 if sum(ismember(poss(i,:),vec))==length(vec)
to do that. However, that is an awkward way of accomplishing this. Just reverse the 'ismember' arguments
 if all(ismember(vec,poss(i,:)))
This is true if every member of 'vec' is present somewhere in 'poss(i,:)' which seems to be what you want.
I would think that, rather than developing a matrix 'e' in the way you have done here. it would be much simpler to create merely a column vector 'e' and subsequently eliminate invalid combinations as follows:
 poss = combntns(tasks,n)
 e = true(size(poss,1),1);
 for i = 1:size(poss,1)
   for j = 1:n
     if ~all(ismember(find(pre(poss(i,j),:)),poss(i,:)))
       e(i) = false;
       break
     end
   end
 end
 valid = poss(e,:);
Related Question