Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: generation of random multiset permutation with restrictions
Replies: 17   Last Post: Jan 30, 2013 6:41 AM

 Messages: [ Previous | Next ]
 Michal Kvasnicka Posts: 62 Registered: 5/7/10
Re: generation of random multiset permutation with restrictions
Posted: Aug 10, 2012 4:01 AM

"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!

Date Subject Author
8/9/12 Michal Kvasnicka
8/10/12 Bruno Luong
8/10/12 Michal Kvasnicka
8/21/12 Michal Kvasnicka
8/21/12 Bruno Luong
8/21/12 Michal Kvasnicka
8/21/12 Bruno Luong
8/21/12 Michal Kvasnicka
8/21/12 Bruno Luong
8/21/12 Michal Kvasnicka
8/21/12 Bruno Luong
8/23/12 Michal Kvasnicka
1/29/13 Michal Kvasnicka
1/30/13 Michal Kvasnicka
1/30/13 Bruno Luong
1/30/13 Michal Kvasnicka
1/30/13 Bruno Luong
1/30/13 Michal Kvasnicka