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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
5
$\begingroup$

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

Improve this answer
$\endgroup$
4
  • $\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.
    Commented Mar 7, 2019 at 2:57
  • $\begingroup$ (very neat solution, by the way) $\endgroup$
    – Clement C.
    Commented Mar 7, 2019 at 3:07
  • $\begingroup$ No worries and thanks. $\endgroup$
    – Michael Albert
    Commented Mar 7, 2019 at 18:48
  • $\begingroup$ Accepting this answer as it addresses my original question. $\endgroup$
    – Clement C.
    Commented Mar 9, 2019 at 17:38

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .