Safe Haskell | None |
---|

Partitions. Partitions are nonincreasing sequences of positive integers.

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

- data Partition
- toPartition :: [Int] -> Partition
- toPartitionUnsafe :: [Int] -> Partition
- mkPartition :: [Int] -> Partition
- isPartition :: [Int] -> Bool
- fromPartition :: Partition -> [Int]
- height :: Partition -> Int
- width :: Partition -> Int
- heightWidth :: Partition -> (Int, Int)
- weight :: Partition -> Int
- dualPartition :: Partition -> Partition
- _dualPartition :: [Int] -> [Int]
- elements :: Partition -> [(Int, Int)]
- _elements :: [Int] -> [(Int, Int)]
- countAutomorphisms :: Partition -> Integer
- _countAutomorphisms :: [Int] -> Integer
- partitions' :: (Int, Int) -> Int -> [Partition]
- _partitions' :: (Int, Int) -> Int -> [[Int]]
- countPartitions' :: (Int, Int) -> Int -> Integer
- partitions :: Int -> [Partition]
- _partitions :: Int -> [[Int]]
- countPartitions :: Int -> Integer
- allPartitions' :: (Int, Int) -> [[Partition]]
- allPartitions :: Int -> [[Partition]]
- countAllPartitions' :: (Int, Int) -> Integer
- countAllPartitions :: Int -> Integer
- partitionMultiset :: (Eq a, Ord a) => [a] -> [[[a]]]
- type IntVector = UArray Int Int
- vectorPartitions :: IntVector -> [[IntVector]]
- _vectorPartitions :: [Int] -> [[[Int]]]
- fasc3B_algorithm_M :: [Int] -> [[IntVector]]

# Type and basic stuff

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

toPartition :: [Int] -> PartitionSource

Checks whether the input is a 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...

fromPartition :: Partition -> [Int]Source

heightWidth :: Partition -> (Int, Int)Source

weight :: Partition -> IntSource

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

dualPartition :: Partition -> PartitionSource

The dual (or conjugate) partition.

_dualPartition :: [Int] -> [Int]Source

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

countAutomorphisms :: Partition -> IntegerSource

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

_countAutomorphisms :: [Int] -> IntegerSource

# Generation

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

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

countPartitions :: Int -> IntegerSource

All partitions fitting into a given rectangle.

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

All partitions up to a given degree.

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

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

# Paritions of multisets, vector partitions

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

Partitions of a multiset.

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

Vector partitions. Basically a synonym for `fasc3B_algorithm_M`

.

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

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

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