debugMinor
An iterative algorithm for finding the partitions of a set into subsets of a fixed size
Viewed 0 times
theiterativeintosizesubsetsalgorithmpartitionsforfindingfixed
Problem
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.
Solution
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] 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)$.
Then swap $b_{i,j}[1]$ and $x$ and return $j$.
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.
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] 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.
Context
StackExchange Computer Science Q#117425, answer score: 2
Revisions (0)
No revisions yet.