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.
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
What's wrong? Are you looking for something like:
tril(ones(10),-1)
采纳的回答
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,:);
Gökhan Kof
2013-1-13
更多回答（0 个）
类别
在 帮助中心 和 File Exchange 中查找有关 Code Performance 的更多信息
2013-1-11
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!
Translated by 
