exact-cover-0.1.0.0: Efficient exact cover solver.

Math.ExactCover

Description

This module provides an efficient solver for exact set cover problems (http://en.wikipedia.org/wiki/Exact_cover) using Algorithm X as described in the paper Dancing Links, by Donald Knuth, in Millennial Perspectives in Computer Science, P159, 2000 (https://arxiv.org/abs/cs/0011047).

For a quick start, go straight to the solve function.

Synopsis

# Mathematical definition

Given a collection $$\mathcal{S}$$ of subsets of a set $$\mathcal{X}$$, an exact cover is a subcollection $$\mathcal{S}^{*}$$ of $$\mathcal{S}$$ such that each element in $$\mathcal{X}$$ is contained in exactly one subset in $$\mathcal{S}^{*}$$ (from wikipedia).

# Simple interface

solve :: (Enum a, Ord a) => Map (Set a) setlabel -> [setlabel] Source #

Given a collection of subsets $$\mathcal{S}$$, represented by a Map between each subset (of type Set a) and its label, returns a list of labels that represents the exact cover $$\mathcal{S}^{*}$$.

Example: To find the exact cover of the collection of subsets $$\left\{\left\{2,4,5\right\}, \left\{0,3,6\right\}, \left\{1,2,5\right\}, \left\{0,3\right\}, \left\{1,6\right\}, \left\{3,4,6\right\}\right\}$$,

solve (Map.fromList [ (Set.fromList [2,4,5], 'A')
, (Set.fromList [0,3,6], 'B')
, (Set.fromList [1,2,5], 'C')
, (Set.fromList [0,3], 'D')
, (Set.fromList [1,6], 'E')
, (Set.fromList [3,4,6], 'F')
] :: Map (Set Int) Char)
== "DAE"

# Types

data ExactCoverProblem setlabel a Source #

Basic type that represents the exact cover problem.

# Construction

transform :: Enum a => Map (Set a) setlabel -> ExactCoverProblem setlabel a Source #

Constructs an ExactCoverProblem given a collection of subsets $$\mathcal{S}$$ as represented by a Map between each subset and its label. The set $$\mathcal{X}$$ over which the exact cover is to be found is assumed to be the union of the given collection of subsets $$\mathcal{S}$$.

# Solvers

solveEC :: (Enum a, Ord a) => ExactCoverProblem setlabel a -> [setlabel] Source #

Solves the given ExactCoverProblem, returning the labels of the subsets that form the exact cover.