Safe Haskell	None
Language	Haskell98

Math.Combinatorics.Poset

Synopsis

newtype Poset t = Poset ([t], t -> t -> Bool)
implies :: Bool -> Bool -> Bool
isReflexive :: ([t], t -> t -> Bool) -> Bool
isAntisymmetric :: Eq a => ([a], a -> a -> Bool) -> Bool
isTransitive :: ([t], t -> t -> Bool) -> Bool
isPoset :: Eq t => ([t], t -> t -> Bool) -> Bool
poset :: Eq t => ([t], t -> t -> Bool) -> Poset t
intervals :: Poset b -> [(b, b)]
interval :: Poset a -> (a, a) -> [a]
chainN :: Int -> Poset Int
antichainN :: Int -> Poset Int
divides :: Integral a => a -> a -> Bool
divisors :: Integral a => a -> [a]
posetD :: Int -> Poset Int
powerset :: [a] -> [[a]]
posetB :: Int -> Poset [Int]
partitions :: [a] -> [[[a]]]
isRefinement :: Ord a => [[a]] -> [[a]] -> Bool
posetP :: Int -> Poset [[Int]]
intervalPartitions :: (Eq a, Num a) => [a] -> [[[a]]]
isInterval :: (Eq a, Num a) => [a] -> Bool
intervalPartitions2 :: [a] -> [[[a]]]
integerPartitions :: (Ord a, Num a) => a -> [[a]]
isIPRefinement :: (Ord a, Num a) => [a] -> [a] -> Bool
posetIP :: Int -> Poset [Int]
subspaces :: (Eq a, Num a) => [a] -> Int -> [[[a]]]
isSubspace :: (Foldable t, Eq a, Num a) => t [a] -> [[a]] -> Bool
posetL :: (Eq fq, Num fq) => Int -> [fq] -> Poset [[fq]]
subposet :: Poset a -> (a -> Bool) -> Poset a
dsum :: Poset a -> Poset b -> Poset (Either a b)
dprod :: Poset a -> Poset b -> Poset (a, b)
dual :: Poset a -> Poset a
hasseDigraph :: Eq a => Poset a -> Digraph a
reachabilityPoset :: Ord a => Digraph a -> Poset a
isOrderPreserving :: (a -> b) -> Poset a -> Poset b -> Bool
orderIsos01 :: Poset a1 -> Poset a2 -> [[(a1, a2)]]
isOrderIso :: (Ord a, Ord b) => Poset a -> Poset b -> Bool
orderIsos :: (Ord a, Ord b) => Poset a -> Poset b -> [[(a, b)]]
orderAuts1 :: Ord b => Poset b -> [[(b, b)]]
isLinext :: Poset t -> [t] -> Bool
linexts :: Poset t -> [[t]]

Documentation

newtype Poset t Source #

A poset is represented as a pair (set,po), where set is the underlying set of the poset, and po is the partial order relation

Constructors

Poset ([t], t -> t -> Bool)

Instances

Eq t => Eq (Poset t) Source #
Instance details Defined in Math.Combinatorics.Poset Methods (==) :: Poset t -> Poset t -> Bool # (/=) :: Poset t -> Poset t -> Bool #
Show t => Show (Poset t) Source #
Instance details Defined in Math.Combinatorics.Poset Methods showsPrec :: Int -> Poset t -> ShowS # show :: Poset t -> String # showList :: [Poset t] -> ShowS #

implies :: Bool -> Bool -> Bool Source #

isReflexive :: ([t], t -> t -> Bool) -> Bool Source #

isAntisymmetric :: Eq a => ([a], a -> a -> Bool) -> Bool Source #

isTransitive :: ([t], t -> t -> Bool) -> Bool Source #

isPoset :: Eq t => ([t], t -> t -> Bool) -> Bool Source #

poset :: Eq t => ([t], t -> t -> Bool) -> Poset t Source #

intervals :: Poset b -> [(b, b)] Source #

interval :: Poset a -> (a, a) -> [a] Source #

chainN :: Int -> Poset Int Source #

A chain is a poset in which every pair of elements is comparable (ie either x <= y or y <= x). It is therefore a linear or total order. chainN n is the poset consisting of the numbers [1..n] ordered by (<=)

antichainN :: Int -> Poset Int Source #

An antichain is a poset in which distinct elements are incomparable. antichainN n is the poset consisting of [1..n], with x <= y only when x == y.

divides :: Integral a => a -> a -> Bool Source #

divisors :: Integral a => a -> [a] Source #

posetD :: Int -> Poset Int Source #

posetD n is the lattice of (positive) divisors of n

powerset :: [a] -> [[a]] Source #

posetB :: Int -> Poset [Int] Source #

posetB n is the lattice of subsets of [1..n] ordered by inclusion

partitions :: [a] -> [[[a]]] Source #

isRefinement :: Ord a => [[a]] -> [[a]] -> Bool Source #

posetP :: Int -> Poset [[Int]] Source #

posetP n is the lattice of set partitions of [1..n], ordered by refinement

intervalPartitions :: (Eq a, Num a) => [a] -> [[[a]]] Source #

isInterval :: (Eq a, Num a) => [a] -> Bool Source #

intervalPartitions2 :: [a] -> [[[a]]] Source #

integerPartitions :: (Ord a, Num a) => a -> [[a]] Source #

isIPRefinement :: (Ord a, Num a) => [a] -> [a] -> Bool Source #

posetIP :: Int -> Poset [Int] Source #

posetIP n is the poset of integer partitions of n, ordered by refinement

subspaces :: (Eq a, Num a) => [a] -> Int -> [[[a]]] Source #

isSubspace :: (Foldable t, Eq a, Num a) => t [a] -> [[a]] -> Bool Source #

posetL :: (Eq fq, Num fq) => Int -> [fq] -> Poset [[fq]] Source #

posetL n fq is the lattice of subspaces of the vector space Fq^n, ordered by inclusion. Subspaces are represented by their reduced row echelon form. Example usage: posetL 2 f3

subposet :: Poset a -> (a -> Bool) -> Poset a Source #

The subposet of a poset satisfying a predicate

dsum :: Poset a -> Poset b -> Poset (Either a b) Source #

The direct sum of two posets

dprod :: Poset a -> Poset b -> Poset (a, b) Source #

The direct product of two posets

dual :: Poset a -> Poset a Source #

The dual of a poset

hasseDigraph :: Eq a => Poset a -> Digraph a Source #

Given a poset (X,<=), we say that y covers x, written x -< y, if x < y and there is no z in X with x < z < y. The Hasse digraph of a poset is the digraph whose vertices are the elements of the poset, with an edge between every pair (x,y) with x -< y. The Hasse digraph can be represented diagrammatically as a Hasse diagram, by drawing x below y whenever x -< y.

reachabilityPoset :: Ord a => Digraph a -> Poset a Source #

Given a DAG (directed acyclic graph), return the poset consisting of the vertices of the DAG, ordered by reachability. This can be used to recover a poset from its Hasse digraph.

isOrderPreserving :: (a -> b) -> Poset a -> Poset b -> Bool Source #

orderIsos01 :: Poset a1 -> Poset a2 -> [[(a1, a2)]] Source #

isOrderIso :: (Ord a, Ord b) => Poset a -> Poset b -> Bool Source #

Are the two posets order-isomorphic?

orderIsos :: (Ord a, Ord b) => Poset a -> Poset b -> [[(a, b)]] Source #

Find all order isomorphisms between two posets

orderAuts1 :: Ord b => Poset b -> [[(b, b)]] Source #

isLinext :: Poset t -> [t] -> Bool Source #

A linear extension of a poset is a linear ordering of the elements which extends the partial order. Equivalently, it is an ordering [x1..xn] of the underlying set, such that if xi <= xj then i <= j.

linexts :: Poset t -> [[t]] Source #

Linear extensions of a poset