Safe Haskell | None |
---|---|
Language | Haskell2010 |
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]]
- 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.
NonCrossing [[Int]] |
_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
:: Int |
|
-> Int |
|
-> [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
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