Safe Haskell | None |
---|---|
Language | Haskell2010 |
Partitions of integers. Integer partitions are nonincreasing sequences of positive integers.
See:
- Donald E. Knuth: The Art of Computer Programming, vol 4, pre-fascicle 3B.
- http://en.wikipedia.org/wiki/Partition_(number_theory)
For example the partition
Partition [8,6,3,3,1]
can be represented by the (English notation) Ferrers diagram:
- newtype Partition = Partition [Int]
- class HasNumberOfParts p where
- numberOfParts :: p -> Int
- mkPartition :: [Int] -> Partition
- toPartitionUnsafe :: [Int] -> Partition
- toPartition :: [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
- dominates :: Partition -> Partition -> Bool
- _partitions' :: (Int, Int) -> Int -> [[Int]]
- partitions' :: (Int, Int) -> Int -> [Partition]
- countPartitions' :: (Int, Int) -> Int -> Integer
- _partitions :: Int -> [[Int]]
- partitions :: Int -> [Partition]
- countPartitions :: Int -> Integer
- allPartitions' :: (Int, Int) -> [[Partition]]
- allPartitions :: Int -> [[Partition]]
- countAllPartitions' :: (Int, Int) -> Integer
- countAllPartitions :: Int -> Integer
- partitionsWithKParts :: Int -> Int -> [Partition]
- countPartitionsWithKParts :: Int -> Int -> Integer
- isSubPartitionOf :: Partition -> Partition -> Bool
- subPartitions :: Int -> Partition -> [Partition]
- _subPartitions :: Int -> [Int] -> [[Int]]
- allSubPartitions :: Partition -> [Partition]
- _allSubPartitions :: [Int] -> [[Int]]
- data PartitionConvention
- asciiFerrersDiagram :: Partition -> ASCII
- asciiFerrersDiagram' :: PartitionConvention -> Char -> Partition -> ASCII
Type and basic stuff
A partition of an integer. The additional invariant enforced here is that partitions
are monotone decreasing sequences of positive integers. The Ord
instance is lexicographical.
class HasNumberOfParts p where Source
numberOfParts :: p -> Int Source
mkPartition :: [Int] -> Partition Source
Sorts the input, and cuts the nonpositive elements.
toPartitionUnsafe :: [Int] -> Partition Source
Assumes that the input is decreasing.
toPartition :: [Int] -> Partition Source
Checks whether the input is an integer partition. See the note at isPartition
!
isPartition :: [Int] -> Bool Source
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 -> Int Source
The weight of the partition (that is, the sum of the corresponding sequence).
dualPartition :: Partition -> Partition Source
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) ]
Automorphisms
countAutomorphisms :: Partition -> Integer Source
Computes the number of "automorphisms" of a given integer partition.
_countAutomorphisms :: [Int] -> Integer Source
Dominance order
dominates :: Partition -> Partition -> Bool Source
q `dominates` p
returns True
if q >= p
in the dominance order of partitions
(this is partial ordering on the set of partitions of n
).
Generating partitions
Integer partitions of d
, fitting into a given rectangle, as lists.
Partitions of d, fitting into a given rectangle. The order is again lexicographic.
_partitions :: Int -> [[Int]] Source
Partitions of d
, as lists
partitions :: Int -> [Partition] Source
Partitions of d
.
countPartitions :: Int -> Integer Source
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) -> Integer Source
# = \binom { h+w } { h }
countAllPartitions :: Int -> Integer Source
Partitions with given number of parts
Lists partitions of n
into k
parts.
sort (partitionsWithKParts k n) == sort [ p | p <- partitions n , numberOfParts p == k ]
Naive recursive algorithm.
Sub-partitions of a given partition
isSubPartitionOf :: Partition -> Partition -> Bool Source
Returns True
of the first partition is a subpartition (that is, fit inside) of the second.
This includes equality
subPartitions :: Int -> Partition -> [Partition] Source
Sub-partitions of a given partition with the given weight:
sort (subPartitions d q) == sort [ p | p <- partitions d, isSubPartitionOf p q ]
_subPartitions :: Int -> [Int] -> [[Int]] Source
allSubPartitions :: Partition -> [Partition] Source
All sub-partitions of a given partition
_allSubPartitions :: [Int] -> [[Int]] Source
ASCII Ferrers diagrams
data PartitionConvention Source
Which orientation to draw the Ferrers diagrams. For example, the partition [5,4,1] corrsponds to:
In standard English notation:
@@@@@ @@@@ @
In English notation rotated by 90 degrees counter-clockwise:
@ @@ @@ @@ @@@
And in French notation:
@ @@@@ @@@@@
EnglishNotation | English notation |
EnglishNotationCCW | English notation rotated by 90 degrees counterclockwise |
FrenchNotation | French notation (mirror of English notation to the x axis) |
asciiFerrersDiagram :: Partition -> ASCII Source
Synonym for asciiFerrersDiagram' EnglishNotation '@'
Try for example:
autoTabulate RowMajor (Right 8) (map asciiFerrersDiagram $ partitions 9)
asciiFerrersDiagram' :: PartitionConvention -> Char -> Partition -> ASCII Source