Generating possible sets that do not violate some condition
1 view (last 30 days)
Show older comments
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.
2 Comments
Sean de Wolski
on 11 Jan 2013
What's wrong? Are you looking for something like:
tril(ones(10),-1)
Accepted Answer
Roger Stafford
on 12 Jan 2013
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 Comments
Roger Stafford
on 12 Jan 2013
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,:);
More Answers (0)
See Also
Categories
Find more on Logical in Help Center and File Exchange
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!