This is a quick tutorial on how to use the set-cover package to
solve exact cover problems.
Given a set X and collection of subsets of X, S, the exact cover problem asks if there is a sub-collection S' of S s.t. the subsets in S' are pairwise disjoint and their union equals X.
Here are some example exact cover problems we will used to demonstrate how
set-cover works.
Example 1. Consider the flags of nations of the world and the colors contained in in those flags. The set S is colllection of sets of colors, one set for each country. The set X is the set of colors which appear in the national flag of some country.
According to the Wikipedia page "List of flags by color combination", the set X consists of the colors: black, blue, brown, gray, green, orange, purple, red, white and yellow. Here are some examples of subsets which appear in the collection S:
{ red, white } -- for Turkey (or Switzerland)
{ blue, red, yellow } -- for Romania
{ blue, white } -- for Finland
...
An exact cover would be a collection of national flags where no two of them have any colors in common and where every color appears in one of the flags in the collection.
Example 2. Consider the problem of creating a 3x3 [Latin square][2] with the symbols A, B and C.
To model this as an exact cover problem, we create the following definitions:
data Symbol = A | B | C
data Element = Row Int Symbol | Col Int Symbol | Pos Int Int
The subsets in S are two-element sets of the form { Row i s, Col j s, Pos i j } for integers i and j and symbol s (1 <= i,j <= 3). A subset like this corresponds to placing the symbol s at the cell (i,j).
The set X is the 27-element set:
{ Row 1 A, Row 1 B, Row 1 C, -- row 1 must contain A, B and C
Row 2 A, Row 2 B, Row 2 C, -- row 2 must contain A, B and C
Row 3 A, Row 3 B, Row 3 C, -- row 3 must contain A, B and C
Col 1 A, Col 1 B, Col 1 C, -- column 1 must contain A, B and C
Col 2 A, Col 2 B, Col 2 C, -- column 2 must contain A, B and C
Col 3 A, Col 3 B, Col 3 C, -- column 3 must contain A, B and C
Pos 1 1, Pos 1 2, Pos 1 3, -- each position must be filled exactly once
Pos 2 1, Pos 2 2, Pos 3 3,
Pos 3 1, Pos 3 2, Pos 3 3
}
Math.SetCover.Exact deals with labelled sets. A label is just another value
attached to the set. The type of the label can be anything - a String or
an Int. Typically the sets in S are associated with a set of parameters, and
those parameters are used as the label.
The search function returns solutions to the exact cover problem as
a collection of labels. This usually makes it easier to interpret what
the solution means.
In the first example problem we might just use the name of the country as the label. For the second example problem we would probably use the tuple (i,j,s) as the label for a subset.
The label for the subsets can be of any type, so you could even use the set itself as its label.
To create a labelled set, use the Assign constructor. We'll see examples
of how this is done later.
Perform the following steps to solve an exact cover problem:
Step 1. Decide on how to represent your elements. Your element type usually
will need to have an Ord instance (and consequently an Eq instance as well.)
Step 2. Decide on a type for set. The type set needs to be an instance of the
Set class. Typical options are:
Data.Set- an instance of the class
Math.SetCover.Bits.C- currentlyWord8,Word16,Word32andWord64.
Step 3. Decide on what your labels will be.
Step 4. Use the Assign constructor to create all of your labelled sets - this is the collection S.
Step 5. Create the initial State value with initState.
Step 6. Call search to start generating the solutions. The solutions are
returned as a list of labels.
Example 1.
For the national flag color problem we will use:
- type
Colorfor the elements of X Data.Setfor our set implementationStringfor our labels
The code to create the collection S is:
import Math.SetCover.Exact
import qualified Data.Set as Set
data Color = Black | Blue | Brown | Gray | Green | Orange | Purple | Red | White | Yellow
deriving (Show, Eq, Ord)
allSubsets = [ Assign "Turkey" (Set.fromList [ Red, White ]
, Assign "Romania" (Set.fromList [ Blue, Red, Yellow ])
, Assign "Finland" (Set.fromList [ Blue, White ])
, ...
]
state0 = initState allSubsets
solutions = search state0
Example 2
For the Latin square problem we will choose:
- type Element` for the elements of X
Data.Setfor our set implementation(Int,Int,Symbol)for our label type
and the code to set up and solve the problem is:
import Math.SetCover.Exact
import qualified Data.Set as Set
data Symbol = A | B | C
deriving (Show, Eq, Ord)
data Element = Row Int Symbol | Col Int Symbol
deriving (Show, Eq, Ord)
allSubsets = [ Assign (i,j,s) (Set.fromList [ Row i s, Col j s ])
| i <- [1..3], j <- [1..3], s <- [A, B, C] ]
state0 = initState allSubsets
solutions = search state0
Here is an example of using Math.SetCover.BitSet for representing sets.
This is the Detailed Example
problem from the Wikipedia entry for the Exact Cover problem.
import Math.SetCover.Exact
import Math.SetCover.BitSet
import Data.Word (Word8)
import Data.Bits (setBit)
bits :: [Int] -> Math.SetCover.BitSet.Set Word8
bits xs = Math.SetCover.BitSet.Set $ foldl setBit 0 xs
allSubs = [ Assign 'A' (bits [1,4,7])
, Assign 'B' (bits [1,4])
, Assign 'C' (bits [4,5,7])
, Assign 'D' (bits [3,5,6])
, Assign 'E' (bits [2,3,6,7])
, Assign 'F' (bits [2,7])
]
sols = search (initState allSubs)
More examples of exact cover problems solved using
set-exact may be found in the examples directory of
the DARCS repository for the package.
Links:
1: https://hackage.haskell.org/package/set-cover/docs/Math-SetCover-Exact.html#t:Set 2: https://en.wikipedia.org/wiki/Latin_square 3: http://hub.darcs.net/thielema/set-cover/browse/example