combinat-0.2.5.0: Generation of various combinatorial objects.

Safe Haskell None

Math.Combinat.Partitions

Description

Partitions. Partitions are nonincreasing sequences of positive integers.

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

Synopsis

# Type and basic stuff

data Partition Source

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] -> PartitionSource

Checks whether the input is a partition. See the note at `isPartition`!

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

The first element of the sequence.

The length of the sequence.

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

The dual (or conjugate) partition.

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

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

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

# Generation

Arguments

 :: (Int, Int) (height,width) -> Int d -> [Partition]

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

Arguments

 :: (Int, Int) (height,width) -> Int d -> [[Int]]

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

Arguments

 :: (Int, Int) (height,width) -> [[Partition]]

All partitions fitting into a given rectangle.

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

All partitions up to a given degree.

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

# Paritions of multisets, vector partitions

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

Partitions of a multiset.

Integer vectors. The indexing starts from 1.

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.