Safe Haskell	None
Language	Haskell2010

Math.Combinat.Partitions.NonCrossing

Contents

The type of non-crossing partitions
Bijection to Dyck paths
Generating non-crossing partitions

Description

Non-crossing partitions.

See eg. http://en.wikipedia.org/wiki/Noncrossing_partition

Non-crossing partitions of the set [1..n] are encoded as lists of lists in standard form: Entries decreasing in each block and blocks listed in increasing order of their first entries. For example the partition in the diagram

is represented as

NonCrossing [[3],[5,4,2],[7,6,1],[9,8]]

Synopsis

newtype NonCrossing = NonCrossing [[Int]]
_isNonCrossing :: [[Int]] -> Bool
_isNonCrossingUnsafe :: [[Int]] -> Bool
_standardizeNonCrossing :: [[Int]] -> [[Int]]
fromNonCrossing :: NonCrossing -> [[Int]]
toNonCrossingUnsafe :: [[Int]] -> NonCrossing
toNonCrossing :: [[Int]] -> NonCrossing
toNonCrossingMaybe :: [[Int]] -> Maybe NonCrossing
setPartitionToNonCrossing :: SetPartition -> Maybe NonCrossing
dyckPathToNonCrossingPartition :: LatticePath -> NonCrossing
dyckPathToNonCrossingPartitionMaybe :: LatticePath -> Maybe NonCrossing
nonCrossingPartitionToDyckPath :: NonCrossing -> LatticePath
_nonCrossingPartitionToDyckPathMaybe :: [[Int]] -> Maybe LatticePath
nonCrossingPartitions :: Int -> [NonCrossing]
nonCrossingPartitionsWithKParts :: Int -> Int -> [NonCrossing]
countNonCrossingPartitions :: Int -> Integer
countNonCrossingPartitionsWithKParts :: Int -> Int -> Integer
randomNonCrossingPartition :: RandomGen g => Int -> g -> (NonCrossing, g)

The type of non-crossing partitions

newtype NonCrossing Source #

A non-crossing partition of the set [1..n] in standard form: entries decreasing in each block and blocks listed in increasing order of their first entries.

Constructors

NonCrossing [[Int]]

Instances

Eq NonCrossing Source #
Instance details Defined in Math.Combinat.Partitions.NonCrossing Methods (==) :: NonCrossing -> NonCrossing -> Bool # (/=) :: NonCrossing -> NonCrossing -> Bool #
Ord NonCrossing Source #
Instance details Defined in Math.Combinat.Partitions.NonCrossing Methods compare :: NonCrossing -> NonCrossing -> Ordering # (<) :: NonCrossing -> NonCrossing -> Bool # (<=) :: NonCrossing -> NonCrossing -> Bool # (>) :: NonCrossing -> NonCrossing -> Bool # (>=) :: NonCrossing -> NonCrossing -> Bool # max :: NonCrossing -> NonCrossing -> NonCrossing # min :: NonCrossing -> NonCrossing -> NonCrossing #
Read NonCrossing Source #
Instance details Defined in Math.Combinat.Partitions.NonCrossing Methods readsPrec :: Int -> ReadS NonCrossing # readList :: ReadS [NonCrossing] # readPrec :: ReadPrec NonCrossing # readListPrec :: ReadPrec [NonCrossing] #
Show NonCrossing Source #
Instance details Defined in Math.Combinat.Partitions.NonCrossing Methods showsPrec :: Int -> NonCrossing -> ShowS # show :: NonCrossing -> String # showList :: [NonCrossing] -> ShowS #
HasNumberOfParts NonCrossing Source #
Instance details Defined in Math.Combinat.Partitions.NonCrossing Methods numberOfParts :: NonCrossing -> Int Source #

_isNonCrossing :: [[Int]] -> Bool Source #

Checks whether a set partition is noncrossing.

Implementation method: we convert to a Dyck path and then back again, and finally compare. Probably not very efficient, but should be better than a naive check for crosses...)

_isNonCrossingUnsafe :: [[Int]] -> Bool Source #

Warning: This function assumes the standard ordering!

_standardizeNonCrossing :: [[Int]] -> [[Int]] Source #

Convert to standard form: entries decreasing in each block and blocks listed in increasing order of their first entries.

fromNonCrossing :: NonCrossing -> [[Int]] Source #

toNonCrossingUnsafe :: [[Int]] -> NonCrossing Source #

toNonCrossing :: [[Int]] -> NonCrossing Source #

Throws an error if the input is not a non-crossing partition

toNonCrossingMaybe :: [[Int]] -> Maybe NonCrossing Source #

setPartitionToNonCrossing :: SetPartition -> Maybe NonCrossing Source #

If a set partition is actually non-crossing, then we can convert it

Bijection to Dyck paths

dyckPathToNonCrossingPartition :: LatticePath -> NonCrossing Source #

Bijection between Dyck paths and noncrossing partitions

Based on: David Callan: Sets, Lists and Noncrossing Partitions

Fails if the input is not a Dyck path.

dyckPathToNonCrossingPartitionMaybe :: LatticePath -> Maybe NonCrossing Source #

Safe version of dyckPathToNonCrossingPartition

nonCrossingPartitionToDyckPath :: NonCrossing -> LatticePath Source #

The inverse bijection (should never fail proper NonCrossing-s)

_nonCrossingPartitionToDyckPathMaybe :: [[Int]] -> Maybe LatticePath Source #

Safe version nonCrossingPartitionToDyckPath

Generating non-crossing partitions

nonCrossingPartitions :: Int -> [NonCrossing] Source #

Lists all non-crossing partitions of [1..n]

Equivalent to (but orders of magnitude faster than) filtering out the non-crossing ones:

(sort $ catMaybes $ map setPartitionToNonCrossing $ setPartitions n) == sort (nonCrossingPartitions n)

nonCrossingPartitionsWithKParts Source #

Arguments

:: Int	`k` = number of parts
-> Int	`n` = size of the set
-> [NonCrossing]

Lists all non-crossing partitions of [1..n] into k parts.

sort (nonCrossingPartitionsWithKParts k n) == sort [ p | p <- nonCrossingPartitions n , numberOfParts p == k ]

countNonCrossingPartitions :: Int -> Integer Source #

Non-crossing partitions are counted by the Catalan numbers

countNonCrossingPartitionsWithKParts Source #

Arguments

:: Int	`k` = number of parts
-> Int	`n` = size of the set
-> Integer

Non-crossing partitions with k parts are counted by the Naranaya numbers

randomNonCrossingPartition :: RandomGen g => Int -> g -> (NonCrossing, g) Source #

Uniformly random non-crossing partition