# Algorithm to find all feasible partition of a set

By feasible I mean all the sets of the partition belongs to a predefined feasible sets. For example, I what to find a partition of {1,2,3}, and only sets in S = {{1,2}, {1,3}, {1}, {2}, {3,4,5}} is allowed.

Any relevant literature is welcomed.

-
Of course we can eliminate any sets in $S$ that are empty or that are not subsets of the target, $T=\{1,2,3\}$ in your example. If $S$ were all of the nonempty subsets of $T$, the number of solutions you want to find is called Bell's number $B_n$ where $n=|T|$. Since generally there are so many of these to construct, I would guess that a backtracking algorithm (taking candidate subsets from $S$ in some predefined order) would perform adequately. – hardmath Apr 17 '14 at 12:48

In the literature this is called the Exact Cover Problem, and it is among Karp's famous list of 21 NP-complete problems.

Donald Knuth proposed Algorithm X to solve it by formulating the available subsets as rows of a $\{0,1\}$-matrix, where the elements of the target set correspond to columns and $1$-entries to subsets whose row contains that element. A solution is a subset of the rows that contains exactly one $1$ for each column. This approach uses recursion and backtracking to find all solutions, and features an algorithmic idea, Dancing Links, that he credits to Hiroshi Hitotsumatsu and Kōhei Noshita.

Informally we would say to eliminate from the family $S$ of potential partitioning "cells" all but the nonempty subsets of the target $T$ to be covered. Find an element $x$ of $T$ which appears the minimal number of times in our reduced $S$, and choose a set $C \in S$ such that $x \in C$. (The fewer sets $C$ to choose from means the less backtracking we are apt to need. If there are no such sets containing $x$, we have failed and must backtrack if possible to examine other parts of the search tree.)

Now set $T' = T\backslash C$ and $S'$ to those sets in $S$ that are subsets of $T'$, i.e. disjoint from $C$. Apply the algorithm recursively to obtain a partition of $T'$ using the candidates of $S'$. Adjoining $C$ to the partition of $T'$, if one is found, gives a partition of $T$.

Added: Let's illustrate this approach using your example. First we reduce $S$ by dropping the entry $\{3,4,5\}$ since it is not a subset of $T=\{1,2,3\}$ and so cannot form a cell of a partition. Now $S = \{\{1,2\},\{1,3\},\{1\},\{2\}\}$.

Now $1$ is covered three times by $S$, $2$ is covered twice, and $3$ is covered only once. Thus to cover $3$ we are forced to use set $\{1,3\}$ in our partition (exact cover) of $T$.

Define $T'=T\backslash \{1,3\} = \{2\}$, and define $S'$ to be those elements of $S$ that are subsets of $T'$ (or disjoint from $\{1,3\}$), i.e. $S' = \{\{2\}\}$. Apply the algorithm to partition $T'$ using cells from $S'$. Clearly the only choice is to take all of $T'=\{2\}$.

Thus the only solution for the example is the partition $\{1,2,3\} = \{1,3\} \cup \{2\}$.

-
Thank you so much!!! – Joe Li Apr 18 '14 at 13:44