2
$\begingroup$

I have a question related to this one. For $n,p \in \mathbb{N}_+$ such that $p\mid n$, let $\mathcal{P}^{\rm eq}$ be the set of all equipartitions of $n$ in $p$ sets; i.e., in sets of equal size $\frac{n}{p}$.

Is it known how to sample efficiently (i.e., in time polynomial in $n,p$) from the uniform distribution on $\mathcal{P}^{\rm eq}$?

Edit: I had forgotten a key part: can this be done using the optimal (up to constant factors) number of random bits, i.e., $O(n\log p)$ uniformly random bits?

$\endgroup$
5
$\begingroup$

Randomly permute $n$ and then divide into blocks of size $n/p$.

$\endgroup$
  • $\begingroup$ OK, that was dumb of me, I forgot the condition on the number of random bits (i.e., using only $O(n \log p)$ uniformly random bits). I know it's frowned upon to so I will ask: do you mind if I edit my question to add said condition? If you do, I'll accept your answer and ask another one. $\endgroup$ – Clement C. Mar 7 at 2:57
  • $\begingroup$ (very neat solution, by the way) $\endgroup$ – Clement C. Mar 7 at 3:07
  • $\begingroup$ No worries and thanks. $\endgroup$ – Michael Albert Mar 7 at 18:48
  • $\begingroup$ Accepting this answer as it addresses my original question. $\endgroup$ – Clement C. Mar 9 at 17:38

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.