Sampling among constrained partitions I'm working on a clustering problem and want to sample partitions (possible clustering solutions) among a set of constrained ones. 

Here is the problem: I have a set of objects $O=\{o_1,\ldots,o_n\}$ and would like to sample among reflexive, symmetric and transitive relations $R \in O \times O$ such that samples satisfy a set of must-link/cannot-link constraints. More specifically, I do have for some pairs $o_i,o_j$ either that $(o_i,o_j) \in R$ or $(o_i,o_j) \not\in R$. Alternatively, I could see it as the problem of sampling graphs that are disjoint cliques with pre-specified arcs or absences or arcs. 

Reject sampling is likely to not work in practice, as the number of rejection would quickly be prohibitive as n and the set of constraints get high enough (something we can expect). 

Do any of you know if this problem has been treated, or any easy way to solve it? Uniformity within the set of samples is desirable, but not absolutely necessary. 

Thanks.
A reflexive, symmetric and transitive relation $R$ on $O$ is the same as a partition of $O$. If $(o_i,o_j) \in R$ then $o_i,o_j$ are in the same partition, and so can be merged. If $(o_i,o_j) \notin R$ then $o_i,o_j$ are not allowed to be in the same partition. After merging, we reach the following problem:


  Given a graph, partition the set of vertices so that each partition is an independent set.


Equivalently (up to a permutation of colors):


  Given a graph, find a proper coloring.


Intuitively, it seems that a random partition will have many parts, so you can try to generate a random sample in the following way. Greedily sample a "small" independent set whose size you choose in advance as a Poisson random variable with constant expectation, remove it from the graph, and repeat. Of course, this won't be a uniform sample. You can gather statistics in some small cases to see what is a good choice of parameters in this procedure, and whether the results are good enough for your purposes.