Generating possible sets that do not violate some condition

Question

Gökhan Kof 2013-1-11

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/58558-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     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
   0     1     1     0     0     0     0     0     0
   0     1     1     1     0     0     0     0     0
   1     0     0     0     0     0     0     0     0
   1     1     1     1     1     1     0     0     0
   1     1     1     1     1     1     1     0     0
   1     1     1     1     1     1     1     1     0

Thanks for your help in advance.

2 个评论
显示无隐藏无

Matt J 2013-1-11

There is a problem up to now.

You haven't mentioned what that problem is.

Sean de Wolski 2013-1-11

在 MATLAB Online 中打开

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

tril(ones(10),-1)

请先登录，再进行评论。

请先登录，再回答此问题。

Answer 1

Roger Stafford 2013-1-12

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/58558-generating-possible-sets-that-do-not-violate-some-condition#answer_70879

在 MATLAB Online 中打开

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

2 个评论
显示无隐藏无

Roger Stafford 2013-1-12

在 MATLAB Online 中打开

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 2013-1-13

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.

请先登录，再进行评论。