Math.Combinat.Partitions

Partitions of integers and multisets. Integer partitions are nonincreasing sequences of positive integers.

See also Donald E. Knuth: The Art of Computer Programming, vol 4, pre-fascicle 3B.

Type and basic stuff

data Partition

A partition of an integer. The additional invariant enforced here is that partitions are monotone decreasing sequences of positive integers.

Instances

Eq Partition

Ord Partition

Read Partition

Show Partition

toPartition :: [Int] -> Partition

Checks whether the input is an integer partition. See the note at isPartition!

toPartitionUnsafe :: [Int] -> Partition

Assumes that the input is decreasing.

mkPartition :: [Int] -> Partition

Sorts the input, and cuts the nonpositive elements.

isPartition :: [Int] -> Bool

Note: we only check that the sequence is ordered, but we do not check for negative elements. This can be useful when working with symmetric functions. It may also change in the future...

fromPartition :: Partition -> [Int]

height :: Partition -> Int

The first element of the sequence.

width :: Partition -> Int

The length of the sequence.

heightWidth :: Partition -> (Int, Int)

weight :: Partition -> Int

The weight of the partition (that is, the sum of the corresponding sequence).

dualPartition :: Partition -> Partition

The dual (or conjugate) partition.

_dualPartition :: [Int] -> [Int]

elements :: Partition -> [(Int, Int)]

Example:

elements (toPartition [5,4,1]) ==
[ (1,1), (1,2), (1,3), (1,4), (1,5)
, (2,1), (2,2), (2,3), (2,4)
, (3,1)
]

_elements :: [Int] -> [(Int, Int)]

countAutomorphisms :: Partition -> Integer

Computes the number of "automorphisms" of a given integer partition.

_countAutomorphisms :: [Int] -> Integer

Generation

partitions'

Arguments

:: (Int, Int)

(height,width)

-> Int

d

-> [Partition]

Partitions of d, fitting into a given rectangle. The order is again lexicographic.

_partitions'

Arguments

:: (Int, Int)

(height,width)

-> Int

d

-> [[Int]]

Integer partitions of d, fitting into a given rectangle, as lists.

countPartitions' :: (Int, Int) -> Int -> Integer

partitions :: Int -> [Partition]

Partitions of d.

_partitions :: Int -> [[Int]]

Partitions of d, as lists

countPartitions :: Int -> Integer

allPartitions'

Arguments

:: (Int, Int)

(height,width)

-> [[Partition]]

All integer partitions fitting into a given rectangle.

allPartitions :: Int -> [[Partition]]

All integer partitions up to a given degree (that is, all integer partitions whose sum is less or equal to d)

countAllPartitions' :: (Int, Int) -> Integer

# = \binom { h+w } { h }

countAllPartitions :: Int -> Integer

Ferrer diagrams

printFerrerDiagram :: Partition -> IO ()

ferrerDiagram :: Partition -> String

Synonym for ferrerDiagramEnglishNotation

ferrerDiagramEnglishNotation :: Partition -> String

ferrerDiagramFrenchNotation :: Partition -> String

ferrerDiagramEnglishNotation' :: Char -> Partition -> String

ferrerDiagramFrenchNotation' :: Char -> Partition -> String

Paritions of multisets, vector partitions

partitionMultiset :: (Eq a, Ord a) => [a] -> [[[a]]]

Partitions of a multiset.

type IntVector = UArray Int Int

Integer vectors. The indexing starts from 1.

vectorPartitions :: IntVector -> [[IntVector]]

Vector partitions. Basically a synonym for fasc3B_algorithm_M.

_vectorPartitions :: [Int] -> [[[Int]]]

fasc3B_algorithm_M :: [Int] -> [[IntVector]]

Generates all vector partitions ("algorithm M" in Knuth). The order is decreasing lexicographic.