Drexel dragonThe Math ForumDonate to the Math Forum



Search All of the Math Forum:

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


Math Forum » Discussions » Software » comp.soft-sys.matlab

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

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
Michal Kvasnicka

Posts: 62
Registered: 5/7/10
Re: generation of random multiset permutation with restrictions
Posted: Aug 21, 2012 4:16 AM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

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


Date Subject Author
8/9/12
Read generation of random multiset permutation with restrictions
Michal Kvasnicka
8/10/12
Read Re: generation of random multiset permutation with restrictions
Bruno Luong
8/10/12
Read Re: generation of random multiset permutation with restrictions
Michal Kvasnicka
8/21/12
Read Re: generation of random multiset permutation with restrictions
Michal Kvasnicka
8/21/12
Read Re: generation of random multiset permutation with restrictions
Bruno Luong
8/21/12
Read Re: generation of random multiset permutation with restrictions
Michal Kvasnicka
8/21/12
Read Re: generation of random multiset permutation with restrictions
Bruno Luong
8/21/12
Read Re: generation of random multiset permutation with restrictions
Michal Kvasnicka
8/21/12
Read Re: generation of random multiset permutation with restrictions
Bruno Luong
8/21/12
Read Re: generation of random multiset permutation with restrictions
Michal Kvasnicka
8/21/12
Read Re: generation of random multiset permutation with restrictions
Bruno Luong
8/23/12
Read Re: generation of random multiset permutation with restrictions
Michal Kvasnicka
1/29/13
Read Re: generation of random multiset permutation with restrictions
Michal Kvasnicka
1/30/13
Read Re: generation of random multiset permutation with restrictions
Michal Kvasnicka
1/30/13
Read Re: generation of random multiset permutation with restrictions
Bruno Luong
1/30/13
Read Re: generation of random multiset permutation with restrictions
Michal Kvasnicka
1/30/13
Read Re: generation of random multiset permutation with restrictions
Bruno Luong
1/30/13
Read Re: generation of random multiset permutation with restrictions
Michal Kvasnicka

Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© Drexel University 1994-2014. All Rights Reserved.
The Math Forum is a research and educational enterprise of the Drexel University School of Education.