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

Defined in Math.Combinat.Partitions.Set

Methods

(==) :: SetPartition -> SetPartition -> Bool

(/=) :: SetPartition -> SetPartition -> Bool

Ord SetPartition

Defined in Math.Combinat.Partitions.Set

Methods

compare :: SetPartition -> SetPartition -> Ordering

(<) :: SetPartition -> SetPartition -> Bool

(<=) :: SetPartition -> SetPartition -> Bool

(>) :: SetPartition -> SetPartition -> Bool

(>=) :: SetPartition -> SetPartition -> Bool

max :: SetPartition -> SetPartition -> SetPartition

min :: SetPartition -> SetPartition -> SetPartition

Read SetPartition

Defined in Math.Combinat.Partitions.Set

Methods

readsPrec :: Int -> ReadS SetPartition

readList :: ReadS [SetPartition]

readPrec :: ReadPrec SetPartition

readListPrec :: ReadPrec [SetPartition]

Show SetPartition

Defined in Math.Combinat.Partitions.Set

Methods

showsPrec :: Int -> SetPartition -> ShowS

show :: SetPartition -> String

showList :: [SetPartition] -> ShowS

HasNumberOfParts SetPartition

Defined in Math.Combinat.Partitions.Set

Methods

numberOfParts :: SetPartition -> Int

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

fromSetPartition :: SetPartition -> [[Int]]

toSetPartitionUnsafe :: [[Int]] -> SetPartition

toSetPartition :: [[Int]] -> SetPartition

_isSetPartition :: [[Int]] -> Bool

Forgetting the set structure

setPartitionShape :: SetPartition -> Partition

The "shape" of a set partition is the partition we get when we forget the set structure, keeping only the cardinalities.

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