combinat- Generation of various combinatorial objects.

Safe HaskellNone




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 Source

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

toPartition :: [Int] -> PartitionSource

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

toPartitionUnsafe :: [Int] -> PartitionSource

Assumes that the input is decreasing.

mkPartition :: [Int] -> PartitionSource

Sorts the input, and cuts the nonpositive elements.

isPartition :: [Int] -> BoolSource

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

height :: Partition -> IntSource

The first element of the sequence.

width :: Partition -> IntSource

The length of the sequence.

weight :: Partition -> IntSource

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

dualPartition :: Partition -> PartitionSource

The dual (or conjugate) partition.

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


 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)]Source

countAutomorphisms :: Partition -> IntegerSource

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




:: (Int, Int)


-> Int


-> [Partition] 

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



:: (Int, Int)


-> Int


-> [[Int]] 

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

partitions :: Int -> [Partition]Source

Partitions of d.

_partitions :: Int -> [[Int]]Source

Partitions of d, as lists



:: (Int, Int)


-> [[Partition]] 

All integer partitions fitting into a given rectangle.

allPartitions :: Int -> [[Partition]]Source

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

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

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

Ferrer diagrams

Paritions of multisets, vector partitions

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

Partitions of a multiset.

type IntVector = UArray Int IntSource

Integer vectors. The indexing starts from 1.

vectorPartitions :: IntVector -> [[IntVector]]Source

Vector partitions. Basically a synonym for fasc3B_algorithm_M.

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

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