An iterative algorithm for finding the partitions of a set into subsets of a fixed size

Question

The question is whether someone could provide an algorithm for finding all the partitions of a set S into subsets of fixed size (assume the fixed size is 2, to make things simpler, in which case the cardinality of S is even) which is iterative and not recursive and which runs in time proportional to the output (and produces no duplicates). The algorithm, being deterministic, will produce the output in some sorted way. Ideally, it is possible to give a partition as input and generate all the partitions that follow the given one in the ordering in which the algorithm outputs the partitions. Please advise if the question is not clear.

Answer 1

Let's first describe a notation for our partitions. Let $p_i$ represent the $i$th partition which is made up of $|S|/2$ disjoint pairs of $S$. We can represent $p_i$ as $$p_i=b_{i,1},b_{i,2},...b_{i,S/2}$$

In order to ensure uniqueness of partitions, we will enforce a sorting on each partition. For each partition $p_i$, each pair in $p_i$ must be sorted. The pairs must also be sorted among themselves i.e.

$$b_{i,j}[0] < b_{i,j}[1] \;\;\text{and} \;\; b_{i,j} < b_{i,j+1} \;\;\forall j$$

The ordering of the partitions is then defined similarly to other lexicographic orderings.

$$p_i > p_{k} \iff \exists j \;\; \text{s.t.}\;\; \forall j'\in[1, j) \;\; b_{i,j}=b_{k,j} \land b_{i,j'}>b_{k,j'}$$

Now, given some partition $p_i$, we can return the next lexicographically larger partition $p_{i+1}$ by using logic similar to the algorithm for obtaining the next permutation of a set of elements. Let us first describe a function $swap(p_i, j)$ and $sort(p_i, j)$.

• $swap(p_i) \rightarrow \;\;$ Find the largest $j$ such that there exists a larger element in any of the pairs $b_{i,j'}$ for $j'>j$. Let $x$ be the smallest such element i.e. $x = \min(\{x'\in b_{i,j'} | j' > j \land x' > b_{i,j}[1]\}).$

Then swap $b_{i,j}[1]$ and $x$ and return $j$.

• $sort(p_i, j) \rightarrow \;\;$ Sort all of the elements from $b_{i,j}[0]$ to $b_{i,S/2}[1]$ i.e. after calling $sort(p_i, j)$, the sequence $b_{i,j}[0], b_{i,j}[1], ..., b_{i,S/2}[0],b_{i,S/2}[1]$ should be non-decreasing.

Now, we claim that given a partition $p_i$, we can obtain $p_{i+1}$ by running $sort(p_i, swap(p_i)+1)$. The reasoning is identical to that of the "next permutation algorithm" - We must find the largest $j$ such that we can swap $b_{i,j}[1]$ with the next largest value while not changing anything in $b_{i,j'}$ for $j' < j$. After the swap, we must sort the remaining elements to ensure that it is the smallest increase possible. If the remaining elements were not sorted, then by sorting them we would obtain a partition greater than $p_i$ but less than $p_{i+1}$, which is a contradiction.