Math.Combinat.Partitions

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

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 a 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,2,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 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]]

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 partitions fitting into a given rectangle.

allPartitions :: Int -> [[Partition]]

All partitions up to a given degree.

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

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

countAllPartitions :: Int -> Integer

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.