| Safe Haskell | None |
|---|---|
| Language | Haskell2010 |
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.
- 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 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.