Safe Haskell  None 

This module provides a solver for exact set cover problems. http://en.wikipedia.org/wiki/Exact_cover
 data Assign label set = Assign {
 label :: label
 labeledSet :: set
 assign :: label > set > Assign label set
 bitVectorFromSetAssigns :: Ord a => [Assign label (Set a)] > [Assign label (Set Integer)]
 intSetFromSetAssigns :: Ord a => [Assign label (Set a)] > [Assign label IntSet]
 partitions :: Set set => [Assign label set] > [[label]]
 search :: Set set => State label set > [[label]]
 step :: Set set => State label set > [State label set]
 data State label set = State {
 availableSubsets :: [Assign label set]
 freeElements :: set
 usedSubsets :: [label]
 initState :: Set set => [Assign label set] > State label set
 updateState :: Set set => Assign label set > State label set > State label set
 class Set set where
 data Tree label set
 decisionTree :: Choose set => [Assign label set] > Tree label set
 completeTree :: Choose set => State label set > Tree label set
 class Set set => Choose set where
 chooseMinimize :: set > [Assign label set] > (set, [Assign label set])
Documentation
Assign
allows to associate a set with a label.
If a particular set is chosen for a set cover,
then its label is included in the output of partitions
.
I have decided to separate sets and labels this way,
since it is the easiest way to assign a meaning to a set.
If you really want to know the sets in a partition,
then you can fill the label
field with the set.
Assign  

bitVectorFromSetAssigns :: Ord a => [Assign label (Set a)] > [Assign label (Set Integer)]Source
You may use this to postprocess a set of Assign
s
in order to speedup the solver considerably.
You must process the whole set of Assign
s at once,
i.e. do not process only parts of the assignment list.
The output of bitVectorFromSetAssigns
should go into the solver as is.
intSetFromSetAssigns :: Ord a => [Assign label (Set a)] > [Assign label IntSet]Source
Like bitVectorFromSetAssigns
but generates IntSet
instead of Integer
bitvectors.
Since containers0.5.5 as shipped with GHC7.8.4,
IntSet
should usually be more efficient than Integer
.
partitions :: Set set => [Assign label set] > [[label]]Source
partitions [assign '0' set0, assign '1' set1, assign '2' set2]
computes unions [set0, set1, set2]
and tries to partition the union set
using the sets set0
, set1
, set2
.
partitions
returns all such partitions.
If a set is chosen for a partition,
then its label is included in the output.
E.g. set0 = Set.fromList [0,1], set1 = Set.fromList [2], set2 = Set.fromList [0,1,2]
,
then partitions
returns [01, 2]
.
The order of partitions and the order of labels depends on the implementation and you must not rely on them.
You may use listToMaybe
in order to select only the first solution.
step :: Set set => State label set > [State label set]Source
This is the key of the search algorithm.
The search algorithm tries to build partitions
by adding sets to a partition list successively.
A step starts on a partial partition
and looks for new sets that could be added.
The goal is to avoid to check a set again down in a search branch
and to quickly determine search directions that lead to a dead end.
To this end a search step selects a certain set element
and tries all sets that contain that element
and that do not overlap with the partial partition.
Practically, step
selects an element with the minimal number
of nonoverlapping sets it is contained in.
If this number is zero, then the search can be aborted in this branch.
Most oftenly the power of the algorithm originates from the formulation of a problem as a setcover problem and from the equal treatment of all elements. E.g. in the Soma cube example the algorithm chooses whether to do a case analysis on all bricks that cover a certain position, or to do a case analysis on all positions that are possible for a certain brick.
The algorithm might not be extraordinarily fast, but in all cases it consumes only little memory since it only has to maintain the current state of search.
Precondition: freeElements
of the input state must not be empty.
The state of the search.
usedSubsets
contains the partial partition built up so far.
availableSubsets
is the list of sets we can still try to put into a partition.
The lists usedSubsets
and availableSubsets
are disjoint,
but their union is not necessarily equal to the list of initially given sets.
There are sets not contained in the partial partition
that overlap with the partial partition.
Those sets are not available for extending the partition.
freeElements
contains the elements that are not covered
by the partial partition in usedSubsets
.
unions usedSubset
and freeElements
are disjoint
and their union is the set of all elements.
State  

This class provides all operations needed for the set cover algorithm.
It allows to use the same algorithm
both for containers
' Set
and for sets represented by bit vectors.
disjoint :: set > set > BoolSource
difference :: set > set > setSource
minimize :: set > [Assign label set] > [Assign label set]Source
minimize free assigns
finds a set element x
from free
that is contained in the least number of sets in assigns
.
Then it returns the assigns where x
is contained in the associated set.
This formulation allows us not to name x
and thus we do not need a second type variable for set
elements
and no type family from set
to its element type.
Unchecked preconditions:
free
must be a superset of all sets in the assign list.
free
must be nonempty.
The assigns
list may be empty.
The output of assigns must be a subsequence of the input assigns,
that is, it must be a subset of the input and it must be in the same order.
This requirement was originally needed by minimize
for Map
,
but currently it is not utilized anywhere.
decisionTree :: Choose set => [Assign label set] > Tree label setSource
completeTree :: Choose set => State label set > Tree label setSource