Data.Partition

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.

Documentation

data Partition a

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)

Defined in Data.Partition

Methods

(==) :: Partition a -> Partition a -> Bool

(/=) :: Partition a -> Partition a -> Bool

Ord a => Ord (Partition a)

Defined in Data.Partition

Methods

compare :: Partition a -> Partition a -> Ordering

(<) :: Partition a -> Partition a -> Bool

(<=) :: Partition a -> Partition a -> Bool

(>) :: Partition a -> Partition a -> Bool

(>=) :: Partition a -> Partition a -> Bool

max :: Partition a -> Partition a -> Partition a

min :: Partition a -> Partition a -> Partition a

Show a => Show (Partition a)

Defined in Data.Partition

Methods

showsPrec :: Int -> Partition a -> ShowS

show :: Partition a -> String

showList :: [Partition a] -> ShowS

discrete :: Partition a

A partition in which every element of a is in its own set. Semantics: [[discrete]] = { { x } | x in a }

empty :: Partition a

Synonym for discrete.

fromSets :: Ord a => [Set a] -> Partition a

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

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]

Returns a list of all nontrivial sets (sets with more than one element) in the partition.

nontrivialRepresentatives :: Partition a -> [a]

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

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.

find :: Ord a => Partition a -> a -> Set a

find p x finds the set that the element x is associated with. Semantics: [[find p x]] = the unique s in p such that x in s.

rep :: Ord a => Partition a -> a -> a

rep p x finds the minimum element in the set containing x.