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]
- mkPartition :: [Int] -> Partition
- toPartitionUnsafe :: [Int] -> Partition
- toPartition :: [Int] -> Partition
- isPartition :: [Int] -> Bool
- isEmptyPartition :: Partition -> Bool
- emptyPartition :: Partition
- fromPartition :: Partition -> [Int]
- partitionHeight :: Partition -> Int
- partitionWidth :: Partition -> Int
- heightWidth :: Partition -> (Int, Int)
- partitionWeight :: 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
- countPartitionsNaive :: Int -> Integer
- partitionCountList :: [Integer]
- partitionCountListNaive :: [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
- randomPartition :: RandomGen g => Int -> g -> (Partition, g)
- randomPartitions :: forall g. RandomGen g => Int -> Int -> g -> ([Partition], g)
- 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
- isSuperPartitionOf :: Partition -> Partition -> Bool
- subPartitions :: Int -> Partition -> [Partition]
- _subPartitions :: Int -> [Int] -> [[Int]]
- allSubPartitions :: Partition -> [Partition]
- _allSubPartitions :: [Int] -> [[Int]]
- superPartitions :: Int -> Partition -> [Partition]
- _superPartitions :: Int -> [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.
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.
isEmptyPartition :: Partition -> Bool Source
fromPartition :: Partition -> [Int] Source
partitionHeight :: Partition -> Int Source
The first element of the sequence.
partitionWidth :: Partition -> Int Source
The length of the sequence (that is, the number of parts).
heightWidth :: Partition -> (Int, Int) Source
partitionWeight :: 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
Number of partitions of n
countPartitionsNaive :: Int -> Integer Source
This uses countPartitions'
, and thus is slow
partitionCountList :: [Integer] Source
Infinite list of number of partitions of 0,1,2,...
This uses the infinite product formula the generating function of partitions, recursively expanding it; it is quite fast.
partitionCountList == map countPartitions [0..]
partitionCountListNaive :: [Integer] Source
Naive infinite list of number of partitions of 0,1,2,...
partitionCountListNaive == map countPartitionsNaive [0..]
This is much slower than the power series expansion above.
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.
Random partitions
randomPartition :: RandomGen g => Int -> g -> (Partition, g) Source
Uniformly random partition of the given weight.
NOTE: This algorithm is effective for small n
-s (say n
up to a few hundred / one thousand it should work nicely),
and the first time it is executed may be slower (as it needs to build the table partitionCountList
first)
Algorithm of Nijenhuis and Wilf (1975); see
- Knuth Vol 4A, pre-fascicle 3B, exercise 47;
- Nijenhuis and Wilf: Combinatorial Algorithms for Computers and Calculators, chapter 10
:: RandomGen g | |
=> Int | number of partitions to generate |
-> Int | the weight of the partitions |
-> g | |
-> ([Partition], g) |
Generates several uniformly random partitions of n
at the same time.
Should be a little bit faster then generating them individually.
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- and super-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
isSuperPartitionOf :: Partition -> Partition -> Bool Source
This is provided for convenience/completeness only, as:
isSuperPartitionOf q p == isSubPartitionOf p q
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
superPartitions :: Int -> Partition -> [Partition] Source
Super-partitions of a given partition with the given weight:
sort (superPartitions d p) == sort [ q | q <- partitions d, isSubPartitionOf p q ]
_superPartitions :: Int -> [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