combinat-0.2.4.1: Generation of various combinatorial objects.Source codeContentsIndex
Math.Combinat.Partitions
Contents
Type and basic stuff
Generation
Paritions of multisets, vector 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
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
data Partition Source
The additional invariant enforced here is that partitions are monotone decreasing sequences of positive integers.
show/hide Instances
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
height :: Partition -> IntSource
The first element of the sequence.
width :: Partition -> IntSource
The length of the sequence.
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,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)]Source
countAutomorphisms :: Partition -> IntegerSource
Computes the number of "automorphisms" of a given partition.
_countAutomorphisms :: [Int] -> IntegerSource
Generation
partitions'Source
:: (Int, Int)(height,width)
-> Intd
-> [Partition]
Partitions of d, fitting into a given rectangle. The order is again lexicographic.
_partitions'Source
:: (Int, Int)(height,width)
-> Intd
-> [[Int]]
Partitions of d, fitting into a given rectangle, as lists.
countPartitions' :: (Int, Int) -> Int -> IntegerSource
partitions :: Int -> [Partition]Source
Partitions of d.
_partitions :: Int -> [[Int]]Source
Partitions of d, as lists
countPartitions :: Int -> IntegerSource
allPartitions'Source
:: (Int, Int)(height,width)
-> [[Partition]]
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 }
countAllPartitions :: Int -> IntegerSource
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.
_vectorPartitions :: [Int] -> [[[Int]]]Source
fasc3B_algorithm_M :: [Int] -> [[IntVector]]Source
Generates all vector partitions ("algorithm M" in Knuth). The order is decreasing lexicographic.
Produced by Haddock version 2.6.1