HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Generating all equal-sized set partitions

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
allequalsizedgeneratingpartitionsset

Problem

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.

Solution

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.

Context

StackExchange Computer Science Q#119324, answer score: 3

Revisions (0)

No revisions yet.