3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ See math.stackexchange.com/questions/640558/… for calculating the total number of such partitions $\endgroup$ – Bryce Kille Nov 22 at 2:11
  • 2
    $\begingroup$ Theoretically speaking a recursive algorithm can be made iterative using a stack (think of how a compiler actually implements recursion). $\endgroup$ – Aryabhata Nov 22 at 3:02
  • $\begingroup$ Could you clarify what you mean by "no recursion" i.e. is the solution permitted to use a stack? $\endgroup$ – Bryce Kille Nov 22 at 3:42
  • $\begingroup$ @BryceKille Assume the fixed size is 2, to simplify the discussion. The recursive solution I know removes 2 elements from the set and finds all partitions of the remaining elements. It then adds the pair using the two removed elements to all of these. And it does that for every pair of elements. This is useless for me because I can’t get even a single partition without having in storage a lot of smaller partitions. What I want is to be able to get one partition at a time, without a storage penalty. I hope this helps $\endgroup$ – EGME Nov 22 at 14:40
  • $\begingroup$ What language? If you are using python I can give you a solution that uses generators $\endgroup$ – Bryce Kille Nov 22 at 14:44
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thank you! ... I will study this in detail $\endgroup$ – EGME Nov 26 at 9:00

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.