Partitioning a set into exactly k blocks [closed]

Question

I have a need for an algorithm to generate all partitions of a set S into exactly k < |S| blocks.

Note: I have already found the algorithm for generating all possible partitions; I just need the k - partition algorithm.

Any idea?

Answer 1

In the comments I suggested stopping "the usual recursive algorithm" at depth k-1, having in mind a 2-level recursion scheme where each outer recursion step was a decision to stop building the current part and start building the next part, and each inner recursion step was a decision to place some element into the current part. This is quite a nice scheme, since it means that the individual k-partitions are generated at the bottom of the recursion tree, so you can operate on them immediately at that point if you want, without having to store them all into a huge array for later processing (though of course you can still do that if you want). The only trick here is to make sure that you don't wind up generating the same partition in more than way -- in particular, by generating two partitions containing the same parts, but with those parts in a different order. That can be avoided by enforcing an ordering on parts. The simplest way is to always add the first (i.e. leftmost) available element whenever you start building a new part -- this guarantees that parts in a partition will be ordered by minimum position of their elements.

But if you don't mind instantiating the full list of k-partitions in memory, there's another way that I think is simpler. The following should be enough to help you put a simple recursive algorithm together:

Consider some element s in S. Every k-partition of S is in exactly one of two categories:

1. s appears in the same part as some other element. In this case, deleting s from that part gives a k-partition of S \ {s}.
2. s appears in a part by itself. In this case, deleting that entire part gives a (k-1)-partition of S \ {s}.

All partitions in case (1) can be formed by adding s to one of the parts in a k-partition of S \ {s}, and all partitions in case (2) can be formed by adding a separate part containing only s to a (k-1)-partition of S \ {s}. Convince yourself that this will generate all k-partitions of S once and once only.

During the recursion, the only boundary case you need to consider is when |S| == k -- in that case, you need to return the single partition consisting of k singleton sets.