Generating possible sets that do not violate some condition

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.

[Matt J]

There is a problem up to now.

You haven't mentioned what that problem is.

[Sean de Wolski]

What's wrong? Are you looking for something like:

tril(ones(10),-1)

Answer 1

[Roger Stafford]

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,:);

[Roger Stafford]

If you'd like to get rid of that inner for-loop, it can be done this way:

 poss = combntns(tasks,n)
 e = false(size(poss,1),1);
 for i = 1:size(poss,1)
  e(i) = all(ismember(any(pre(poss(i,:),:)==1,1),poss(i,:)));
 end
 valid = poss(e,:);

[Gökhan Kof]

Yes, it was definitely awkward :). I solved the problem after just a few moments I posted the question here. But, now I have different problems outside of MATLAB. Thanks for the answers.