4
$\begingroup$

Minor disclaimer: This is my first question here, so I hope it is the right place to put it.


Question: Is there an algorithm to exhaustively generate all set partitions of equal size? That is, I want to list all possible ways to divide a set of $N$ elements into $K$ parts where each part has the same size $\frac{N}{K}$. At best, I want to generate all of these partitions sequentially without generating any duplicates. There are many algorithms to list all divisions of a set into $K$ parts that however do not impose a size constraint on the parts. But I have not found anything on generating set partitions of equal size.

I assume that the elements in the set are labeled using labels $1, ..., K$. For $K = 2$ groups, I can exhaustively list all partitions by sequentially generating all permutations of the group labels in lexicographic order and stop as soon as the first element is $2$ [that is assuming I started with the initial partition $(1, 1, 1, ...., 2, 2, 2)$]. However, for $K > 3$ generating permutations of the labels does work anymore without generating duplicate partitions.

$\endgroup$
3
$\begingroup$

Suppose $N=\{0,\dots,N-1\}$. There are $\binom{N-1}{K-1}$ choices for which elements are equivalent to 0. For each choice of these there are $\binom{N-K-1}{K-1}$ choices for which elements are equivalent to the smallest number not equivalent to 0. And then $\binom{N-2K-1}{K-1}$ for which elements are equivalent to the smallest number not equivalent to any number chosen so far. Continuing to iterate this way, we get through all the $\prod_{a=0}^{N/K-1}\binom{N-aK-1}{K-1}$ balanced partitions.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks a lot for this response; I think I will have to "digest" it a bit before accepting the answer (will try to implement it to better understand what you mean). Do you by any chance have a reference for your method or did you just come up with? $\endgroup$ – M. Papenberg Jan 8 at 19:08
  • $\begingroup$ I just came up with it but it's probably/surely been done before $\endgroup$ – Bjørn Kjos-Hanssen Jan 8 at 21:24
  • $\begingroup$ Sorry, but I have to ask for a clarification: What do you exactly mean by "choice"? Selecting one possible partition? In this case, what would it mean that elements in this choice are equivalent to 0? $\endgroup$ – M. Papenberg Jan 9 at 8:42
  • 1
    $\begingroup$ Yes, and equivalent to 0 means: in the same part as 0. $\endgroup$ – Bjørn Kjos-Hanssen Jan 9 at 16:50
  • $\begingroup$ ah I see, thanks a lot! $\endgroup$ – M. Papenberg Jan 10 at 8:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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