Generating possible sets that do not violate some condition
2 次查看(过去 30 天)
显示 更早的评论
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.
采纳的回答
Roger Stafford
2013-1-12
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
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,:);
更多回答(0 个)
另请参阅
类别
在 Help Center 和 File Exchange 中查找有关 Logical 的更多信息
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!