1
$\begingroup$

I'm looking for an algorithm to generate/enumerate all possibilities for partitioning a set of size $n$ to $k$ non-empty subsets, each with size at most $b$.

More specifically, given a set $V$ where $|V|=n$, how to enumerate all possibilities to choose subsets $X_1, ..., X_k \subseteq V$ such that

1) $1 \leq |X_i| \leq b$,

2) $\forall_{i \neq j} X_i,X_j :$ $X_i \cap X_j = \emptyset$,

3) $\bigcup_{i \in \{1,...,k\}} X_i = V$,

Two partitioning are different if they do not have exactly same subsets. The order of subsets doesn't matter.

Can anyone suggest an approach to enumerate such partitioning?

$\endgroup$
  • $\begingroup$ This is a programming exercise. Think how you'd list them by hand, and use the same algorithm. $\endgroup$ – Yuval Filmus Mar 27 '18 at 6:49

Your Answer

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

Browse other questions tagged or ask your own question.