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
- data Pair = Pair !Int !Int
- _dualPartition :: [Int] -> [Int]
- _dualPartitionNaive :: [Int] -> [Int]
- diffSequence :: [Int] -> [Int]
- elements :: Partition -> [(Int, Int)]
- _elements :: [Int] -> [(Int, Int)]
- toExponentialForm :: Partition -> [(Int, Int)]
- _toExponentialForm :: [Int] -> [(Int, Int)]
- fromExponentialFrom :: [(Int, Int)] -> Partition
- countAutomorphisms :: Partition -> Integer
- _countAutomorphisms :: [Int] -> Integer
- partitions :: Int -> [Partition]
- _partitions :: Int -> [[Int]]
- countPartitions :: Int -> Integer
- allPartitions :: Int -> [Partition]
- allPartitionsGrouped :: Int -> [[Partition]]
- allPartitions' :: (Int, Int) -> [Partition]
- allPartitionsGrouped' :: (Int, Int) -> [[Partition]]
- countAllPartitions' :: (Int, Int) -> Integer
- countAllPartitions :: Int -> Integer
- _partitions' :: (Int, Int) -> Int -> [[Int]]
- partitions' :: (Int, Int) -> Int -> [Partition]
- countPartitions' :: (Int, Int) -> Int -> Integer
- dominates :: Partition -> Partition -> Bool
- dominatedPartitions :: Partition -> [Partition]
- _dominatedPartitions :: [Int] -> [[Int]]
- dominatingPartitions :: Partition -> [Partition]
- _dominatingPartitions :: [Int] -> [[Int]]
- partitionsWithKParts :: Int -> Int -> [Partition]
- countPartitionsWithKParts :: Int -> Int -> Integer
- partitionsWithOddParts :: Int -> [Partition]
- partitionsWithDistinctParts :: Int -> [Partition]
- isSubPartitionOf :: Partition -> Partition -> Bool
- subPartitions :: Int -> Partition -> [Partition]
- _subPartitions :: Int -> [Int] -> [[Int]]
- allSubPartitions :: Partition -> [Partition]
- _allSubPartitions :: [Int] -> [[Int]]
- pieriRule :: Partition -> Int -> [Partition]
- dualPieriRule :: Partition -> Int -> [Partition]
- 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
This returns True
if the input is non-increasing sequence of
positive integers (possibly empty); False
otherwise.
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
_dualPartitionNaive :: [Int] -> [Int] Source
A simpler, but bit slower (about twice?) implementation of dual partition
diffSequence :: [Int] -> [Int] Source
From a sequence [a1,a2,..,an]
computes the sequence of differences
[a1-a2,a2-a3,...,an-0]
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) ]
Exponential form
toExponentialForm :: Partition -> [(Int, Int)] Source
We convert a partition to exponential form.
(i,e)
mean (i^e)
; for example [(1,4),(2,3)]
corresponds to (1^4)(2^3) = [2,2,2,1,1,1,1]
. Another example:
toExponentialForm (Partition [5,5,3,2,2,2,2,1,1]) == [(1,2),(2,4),(3,1),(5,2)]
_toExponentialForm :: [Int] -> [(Int, Int)] Source
fromExponentialFrom :: [(Int, Int)] -> Partition Source
Automorphisms
countAutomorphisms :: Partition -> Integer Source
Computes the number of "automorphisms" of a given integer partition.
_countAutomorphisms :: [Int] -> Integer Source
Generating partitions
partitions :: Int -> [Partition] Source
Partitions of d
.
_partitions :: Int -> [[Int]] Source
Partitions of d
, as lists
countPartitions :: Int -> Integer Source
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
)
allPartitionsGrouped :: Int -> [[Partition]] Source
All integer partitions up to a given degree (that is, all integer partitions whose sum is less or equal to d
),
grouped by weight
All integer partitions fitting into a given rectangle.
All integer partitions fitting into a given rectangle, grouped by weight.
countAllPartitions' :: (Int, Int) -> Integer Source
# = \binom { h+w } { h }
countAllPartitions :: Int -> Integer Source
Integer partitions of d
, fitting into a given rectangle, as lists.
Partitions of d, fitting into a given rectangle. The order is again lexicographic.
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
).
dominatedPartitions :: Partition -> [Partition] Source
Lists all partitions of the same weight as lambda
and also dominated by lambda
(that is, all partial sums are less or equal):
dominatedPartitions lam == [ mu | mu <- partitions (weight lam), lam `dominates` mu ]
_dominatedPartitions :: [Int] -> [[Int]] Source
dominatingPartitions :: Partition -> [Partition] Source
Lists all partitions of the sime weight as mu
and also dominating mu
(that is, all partial sums are greater or equal):
dominatingPartitions mu == [ lam | lam <- partitions (weight mu), lam `dominates` mu ]
_dominatingPartitions :: [Int] -> [[Int]] 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.
Partitions with only odd/distinct parts
partitionsWithOddParts :: Int -> [Partition] Source
Partitions of n
with only odd parts
partitionsWithDistinctParts :: Int -> [Partition] Source
Partitions of n
with distinct parts.
Note:
length (partitionsWithDistinctParts d) == length (partitionsWithOddParts d)
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
The Pieri rule
pieriRule :: Partition -> Int -> [Partition] Source
The Pieri rule computes s[lambda]*h[n]
as a sum of s[mu]
-s (each with coefficient 1).
See for example http://en.wikipedia.org/wiki/Pieri's_formula
dualPieriRule :: Partition -> Int -> [Partition] Source
The dual Pieri rule computes s[lambda]*e[n]
as a sum of s[mu]
-s (each with coefficient 1)
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