Sign up ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|cite|improve this question
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

1 Answer 1

up vote 1 down vote accepted

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\}$.

share|cite|improve this answer
Thank you so much!!! – Joe Li Apr 18 '14 at 13:44

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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