Function Repository Resource:

FindExactCover

Source Notebook

Find row subsets of an input binary matrix that sum to 1 in each column

Contributed by: Bradley Klee

ResourceFunction["FindExactCover"][mat]

finds a row subset of the binary matrix mat which sums to 1 in each column.

ResourceFunction["FindExactCover"][mat,All]

finds all row subsets with sum equal to 1 in each column.

ResourceFunction["FindExactCover"][mat,n]

finds up to n row subsets with sum equal to 1 in each column.

Details

An exact cover is a partitioning of a set of elements into disjoint subsets whose union is exactly the original set.

The exact cover (XC) problem gives an original set along with a list of allowable subsets and asks if any selection of the allowable subsets is an exact cover of the original set. It is an NP complete problem, and very similar to graph clique finding (cf. FindClique).

Here we do not deal with sets and subsets, but rather with binary matrices. The input binary matrix mat lists allowable subsets as rows and set elements as columns, by coding that the k^thelement of the original set is also a member of the j^th listed subset if and only if mat_jk=1. Thus a one's row {1,1,…,1} represents a trivial exact cover.

Sometimes the terms items and options are used in place of column and row headers respectively. The exact cover problem can then be stated as follows: Choose a set of options such that every item is included in exactly one option.

If two options are not disjoint, their respective row sum will have a value exceeding 1 in at least one column. Similarly, if neither of two options includes the k^th item, their respective row sum will have a 0 in the k^th column. Let { j₁,j₂,… }∈𝒪 be a set of options. It is an exact cover if and only if the respective row sum satisfies that

Now define a graph whose vertices are options and whose edges indicate pairwise disjunction. Cliques in the graph represent maximal sets of disjoint options, which can easily be tested for the exact cover property once they are found.

FindExactCover has a Method option for switching between three distinct algorithms:

"DancingLinksX"

Donald Knuth's algorithm

"CliqueToCover"

transforms input to a graph and uses FindClique

"BranchAndPrune"

uses a depth-first search

When using the DancingLinksX method, setting the Heuristic sub-option to either Automatic or "Increment" changes the search order:

{"DancingLinksX","Heuristic"→ Automatic}

Knuth's suggested MRV heuristic

{"DancingLinksX","Heuristic"→ "Increment"}

select right-nearest column

The "MRV heuristic" chooses to cover the next item with the minimal number of associated options.

ResourceFunction["FindExactCover"] ignores empty subsets, i.e. zero's rows of the form {0,0,…,0}.

Examples

Basic Examples (4)

An IdentityMatrix has only one exact cover:

In[1]:=

Out[1]=

List the five set partitions of three objects into disjoint sets:

In[2]:=

Out[2]=

Solve an example problem from Wikipedia:

In[3]:=

With[{coverMatrix = {
{1, 0, 0, 1, 0, 0, 1},
{1, 0, 0, 1, 0, 0, 0},
{0, 0, 0, 1, 1, 0, 1},
{0, 0, 1, 0, 1, 1, 0},
{0, 1, 1, 0, 0, 1, 1},
{0, 1, 0, 0, 0, 0, 1}},
alpha = ToUpperCase[Alphabet[]]},
alpha[[Position[coverMatrix, #][[1, 1]] ]] & /@
ResourceFunction["FindExactCover"][coverMatrix]]

Out[3]=

Find an exact cover of the columns of a 5×4 matrix:

In[4]:=

With[{coverMatrix = Rest[Tuples[{0, 1}, 4][[1 ;; -1 ;; 3]]]},
MatrixForm[coverMatrix] -> MatrixForm[ResourceFunction["FindExactCover"][coverMatrix]]
]

Out[4]=

Test the row sum property:

In[5]:=

Out[5]=

Find all exact covers:

In[6]:=

With[{coverMatrix = Rest[Tuples[{0, 1}, 4][[1 ;; -1 ;; 3]]]},
MatrixForm[coverMatrix] -> Map[
MatrixForm, ResourceFunction["FindExactCover"][coverMatrix, All]
]]

Out[6]=

Scope (1)

Ask for only five results:

In[7]:=

Out[7]=

Options (3)

For small simple inputs, setting the "Heuristic" suboption to "Increment" can get results faster:

In[8]:=

$AbsoluteTiming[SeedRandom[9230482]; ClearSystemCache[]; Reap[ ResourceFunction["FindExactCover"][RandomInteger[1, { 100, 10}], All, Method -> {"DancingLinksX", "Heuristic" -> #}] ] /. {x_, y_} :> Rule[y[[1, 1]], Length[x]] ] & /@ {Automatic, "Increment"}$

Out[8]=

The Automatic heuristic can go noticeably faster for more complex inputs:

In[9]:=

$AbsoluteTiming[SeedRandom[9230482]; ClearSystemCache[]; Reap[ ResourceFunction["FindExactCover"][ RandomChoice[{.3, .7} -> {1, 0}, {100, 10}], All, Method -> {"DancingLinksX", "Heuristic" -> #}] faster ] /. {x_, y_} :> Rule[y[[1, 1]], Length[x]] ] & /@ {Automatic, "Increment"}$