Math.Combinat.Partitions.Set

Set partitions.

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

The type of set partitions

newtype SetPartition

A partition of the set [1..n] (in standard order)

Constructors

SetPartition [[Int]]

Instances

Eq SetPartition

Ord SetPartition

Read SetPartition

Show SetPartition

HasNumberOfParts SetPartition

_standardizeSetPartition :: [[Int]] -> [[Int]]

fromSetPartition :: SetPartition -> [[Int]]

toSetPartitionUnsafe :: [[Int]] -> SetPartition

toSetPartition :: [[Int]] -> SetPartition

_isSetPartition :: [[Int]] -> Bool

Generating set partitions

setPartitions :: Int -> [SetPartition]

Synonym for setPartitionsNaive

setPartitionsWithKParts

Arguments

:: Int

k = number of parts

-> Int

n = size of the set

-> [SetPartition]

Synonym for setPartitionsWithKPartsNaive

sort (setPartitionsWithKParts k n) == sort [ p | p <- setPartitions n , numberOfParts p == k ]

setPartitionsNaive :: Int -> [SetPartition]

List all set partitions of [1..n], naive algorithm

setPartitionsWithKPartsNaive

Arguments

:: Int

k = number of parts

-> Int

n = size of the set

-> [SetPartition]

Set partitions of the set [1..n] into k parts

countSetPartitions :: Int -> Integer

Set partitions are counted by the Bell numbers

countSetPartitionsWithKParts

Arguments

:: Int

k = number of parts

-> Int

n = size of the set

-> Integer

Set partitions of size k are counted by the Stirling numbers of second kind