| Copyright | (c) Luke Palmer 2013 |
|---|---|
| License | BSD3 |
| Maintainer | Luke Palmer <lrpalmer@gmail.com> |
| Stability | experimental |
| Portability | portable |
| Safe Haskell | Safe |
| Language | Haskell98 |
Data.Partition
Description
Disjoint set data structure -- Partition a maintains a collection of
disjoint sets of type a, with the ability to find which set a particular
item belongs to and the ability to merge any two such sets into one.
Synopsis
- data Partition a
- discrete :: Partition a
- empty :: Partition a
- fromSets :: Ord a => [Set a] -> Partition a
- fromDisjointSets :: Ord a => [Set a] -> Partition a
- nontrivialSets :: Partition a -> [Set a]
- nontrivialRepresentatives :: Partition a -> [a]
- joinElems :: Ord a => a -> a -> Partition a -> Partition a
- find :: Ord a => Partition a -> a -> Set a
- rep :: Ord a => Partition a -> a -> a
Documentation
A Partition of a: represents a collection of disjoint sets of a whose
union includes every element of a. Semantics: [[Partition a]] = P(P(a))
where P is the power set operation.
Instances
| Eq a => Eq (Partition a) Source # | |
| Ord a => Ord (Partition a) Source # | |
Defined in Data.Partition | |
| Show a => Show (Partition a) Source # | |
discrete :: Partition a Source #
A partition in which every element of a is in its own set. Semantics:
[[discrete]] = { { x } | x in a }
fromSets :: Ord a => [Set a] -> Partition a Source #
Takes a list of (not necessarily disjoint) sets and constructs a partition that associates all elements shared in any of the sets.
O (n k log n), where k is the maximum set-size and n = l k is the total number of non-discrete elements.
fromDisjointSets :: Ord a => [Set a] -> Partition a Source #
Takes a list of disjoint sets and constructs a partition containing those sets, with every remaining element being given its own set. The precondition is not checked.
O (n log n), where n is the total number of elements in the given sets.
nontrivialSets :: Partition a -> [Set a] Source #
Returns a list of all nontrivial sets (sets with more than one element) in the partition.
nontrivialRepresentatives :: Partition a -> [a] Source #
Returns a list of all representatives (least elements) of nontrivial sets in the partition in ascending order.
nontrivialRepresentatives p = Set.findMin $ nonTrivialSets
joinElems :: Ord a => a -> a -> Partition a -> Partition a Source #
joinElems x y merges the two sets containing x and y into a single set. Semantics:
[[joinElems x y p]] = (p `minus` find x `minus` find y) `union` { find x `union` find y }.
O (max(k log n, k log k)), where k is the size of nontrivial subsets and n is the total number of elements in such sets.