Date: Aug 9, 2012 7:22 AM
Author: Michal Kvasnicka
Subject: generation of random multiset permutation with restrictions

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.