
Re: generation of random multiset permutation with restrictions
Posted:
Aug 21, 2012 4:16 AM


"Michal Kvasnicka" wrote in message <k02f48$vs$1@newscl01ah.mathworks.com>... > "Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <k02c51$lo6$1@newscl01ah.mathworks.com>... > > "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 > > Bruno, thank you very much for your help!!! The Hungarian's assignment perfectly solve may problem. > > Thanks again! Bruno, could you help me once again? I need to perform so called "consistency" check, which mean, that I need to perform check if the current permutation satisfy the predefined restrictions.
Example: 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]};
p1 = {3,1,1,1,2,2,3,3} > OK p2 = {1,3,1,1,2,2,3,3} > not OK
Is there any simple way hot to use effectivelly Hungarian's assignment, too?

