combinat-0.2.8.2: Generate and manipulate various combinatorial objects.

Math.Combinat.Partitions.NonCrossing

Description

Non-crossing partitions.

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

# 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

 Source # Methods Source # Methods Source # Methods Source # MethodsshowList :: [NonCrossing] -> ShowS # Source # Methods

_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.

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

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

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

# Bijection to Dyck paths

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.

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

# Generating non-crossing partitions

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)

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 ]

Non-crossing partitions are counted by the Catalan numbers

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