| Safe Haskell | None |
|---|---|
| Language | Haskell2010 |
Math.Combinat.Partitions.Integer.IntList
Contents
Description
Partition functions working on lists of integers.
It's not recommended to use this module directly.
Synopsis
- _mkPartition :: [Int] -> [Int]
- _isPartition :: [Int] -> Bool
- _dualPartition :: [Int] -> [Int]
- _dualPartitionNaive :: [Int] -> [Int]
- _diffSequence :: [Int] -> [Int]
- _elements :: [Int] -> [(Int, Int)]
- _toExponentialForm :: [Int] -> [(Int, Int)]
- _fromExponentialForm :: [(Int, Int)] -> [Int]
- _partitions :: Int -> [[Int]]
- _allPartitions :: Int -> [[Int]]
- _allPartitionsGrouped :: Int -> [[[Int]]]
- _partitions' :: (Int, Int) -> Int -> [[Int]]
- _randomPartition :: RandomGen g => Int -> g -> ([Int], g)
- _randomPartitions :: forall g. RandomGen g => Int -> Int -> g -> ([[Int]], g)
- _dominates :: [Int] -> [Int] -> Bool
- _dominatedPartitions :: [Int] -> [[Int]]
- _dominatingPartitions :: [Int] -> [[Int]]
- _partitionsWithKParts :: Int -> Int -> [[Int]]
- _partitionsWithOddParts :: Int -> [[Int]]
- _partitionsWithDistinctParts :: Int -> [[Int]]
- _isSubPartitionOf :: [Int] -> [Int] -> Bool
- _isSuperPartitionOf :: [Int] -> [Int] -> Bool
- _subPartitions :: Int -> [Int] -> [[Int]]
- _allSubPartitions :: [Int] -> [[Int]]
- _superPartitions :: Int -> [Int] -> [[Int]]
- _pieriRule :: [Int] -> Int -> [[Int]]
- _dualPieriRule :: [Int] -> Int -> [[Int]]
Type and basic stuff
_mkPartition :: [Int] -> [Int] Source #
Sorts the input, and cuts the nonpositive elements.
_isPartition :: [Int] -> Bool Source #
This returns True if the input is non-increasing sequence of
positive integers (possibly empty); False otherwise.
_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 :: [Int] -> [(Int, Int)] Source #
Example:
_elements [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 :: [Int] -> [(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)]
Generating partitions
_partitions :: Int -> [[Int]] Source #
Partitions of d, as lists
_allPartitions :: Int -> [[Int]] Source #
All integer partitions up to a given degree (that is, all integer partitions whose sum is less or equal to d)
_allPartitionsGrouped :: Int -> [[[Int]]] 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
Integer partitions of d, fitting into a given rectangle, as lists.
Random partitions
_randomPartition :: RandomGen g => Int -> g -> ([Int], 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
Arguments
| :: RandomGen g | |
| => Int | number of partitions to generate |
| -> Int | the weight of the partitions |
| -> g | |
| -> ([[Int]], 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 :: [Int] -> [Int] -> 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 :: [Int] -> [[Int]] 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 ]
_dominatingPartitions :: [Int] -> [[Int]] 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 ]
Partitions with given number of parts
_partitionsWithKParts Source #
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 -> [[Int]] Source #
Partitions of n with only odd parts
_partitionsWithDistinctParts :: Int -> [[Int]] Source #
Partitions of n with distinct parts.
Note:
length (partitionsWithDistinctParts d) == length (partitionsWithOddParts d)
Sub- and super-partitions of a given partition
_isSubPartitionOf :: [Int] -> [Int] -> Bool Source #
Returns True of the first partition is a subpartition (that is, fit inside) of the second.
This includes equality
_isSuperPartitionOf :: [Int] -> [Int] -> Bool Source #
This is provided for convenience/completeness only, as:
isSuperPartitionOf q p == isSubPartitionOf p q
_subPartitions :: Int -> [Int] -> [[Int]] Source #
Sub-partitions of a given partition with the given weight:
sort (subPartitions d q) == sort [ p | p <- partitions d, isSubPartitionOf p q ]
_allSubPartitions :: [Int] -> [[Int]] Source #
All sub-partitions of a given partition
_superPartitions :: Int -> [Int] -> [[Int]] Source #
Super-partitions of a given partition with the given weight:
sort (superPartitions d p) == sort [ q | q <- partitions d, isSubPartitionOf p q ]
The Pieri rule
_pieriRule :: [Int] -> Int -> [[Int]] 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
| We assume here that lambda is a partition (non-increasing sequence of positive integers)!