Safe Haskell | None |
---|---|

Language | Haskell2010 |

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.

- solve :: (Enum a, Ord a) => Map (Set a) setlabel -> [setlabel]
- data ExactCoverProblem setlabel a
- transform :: Enum a => Map (Set a) setlabel -> ExactCoverProblem setlabel a
- solveEC :: (Enum a, Ord a) => ExactCoverProblem setlabel a -> [setlabel]

# 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

) and its label, returns a list of
labels that represents the exact cover \( \mathcal{S}^{*} \).`Set`

a

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.