|
|
Re: generation of random multiset permutation with restrictions
Posted:
Aug 10, 2012 3:10 AM
|
|
"Michal Kvasnicka" wrote in message <k006h5$9e6$1@newscl01ah.mathworks.com>...
> I am looking for MATLAB algorithm how to effectively generate any random multiset permutations with additional restrictions.
>
> Example: I have a multiset of items, for example: {1,1,1,2,2,3,3,3}, and a restricting set of sets, for example {{3},{1,2},{1,2,3},{1,2,3},{1,2,3},{1,2,3},{2,3},{2,3}. So, I am looking for permutations of items, but the first element must be 3, and the second must be 1 or 2, etc.
>
> One such permutation that fits the restrictions is: {3,1,1,1,2,2,3,3}
>
> Of course, any check if the restrictions are consistent, i.g. exist at least one possible permutation will important too.
You might use Hungarian's assignment, one of such implementation is on FEX
http://www.mathworks.com/matlabcentral/fileexchange/6543
a = [1,1,1,2,2,3,3,3]
s = {[3],[1,2],[1,2,3],[1,2,3],[1,2,3],[1,2,3],[2,3],[2,3]};
% Engine
% Shuffle
p = a(randperm(length(a)));
% Distance matrix
D = cellfun(@(x) min(abs(bsxfun(@minus,x(:),p)),[],1), s, 'unif', 0);
D = cat(1,D{:});
[i cost] = assignmentoptimal(D);
if all(i) && cost==0
p = p(i');
disp(p)
else
disp('No solution');
end
% Bruno
|
|
