Safe Haskell  None 

Language  Haskell2010 
Noncrossing partitions.
See eg. http://en.wikipedia.org/wiki/Noncrossing_partition
Noncrossing 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 noncrossing partitions
newtype NonCrossing Source #
A noncrossing partition of the set [1..n]
in standard form:
entries decreasing in each block and blocks listed in increasing order of their first entries.
NonCrossing [[Int]] 
Instances
_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 noncrossing partition
toNonCrossingMaybe :: [[Int]] > Maybe NonCrossing Source #
setPartitionToNonCrossing :: SetPartition > Maybe NonCrossing Source #
If a set partition is actually noncrossing, 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 noncrossing partitions
nonCrossingPartitions :: Int > [NonCrossing] Source #
Lists all noncrossing partitions of [1..n]
Equivalent to (but orders of magnitude faster than) filtering out the noncrossing ones:
(sort $ catMaybes $ map setPartitionToNonCrossing $ setPartitions n) == sort (nonCrossingPartitions n)
nonCrossingPartitionsWithKParts Source #
:: Int 

> Int 

> [NonCrossing] 
Lists all noncrossing partitions of [1..n]
into k
parts.
sort (nonCrossingPartitionsWithKParts k n) == sort [ p  p < nonCrossingPartitions n , numberOfParts p == k ]
countNonCrossingPartitions :: Int > Integer Source #
Noncrossing partitions are counted by the Catalan numbers
countNonCrossingPartitionsWithKParts Source #
Noncrossing partitions with k
parts are counted by the Naranaya numbers
randomNonCrossingPartition :: RandomGen g => Int > g > (NonCrossing, g) Source #
Uniformly random noncrossing partition