Math.Combinat.Partitions.Integer

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:

Documentation

module Math.Combinat.Partitions.Integer.Naive

Types and basic stuff

data Partition

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.

Instances

Eq Partition

Defined in Math.Combinat.Partitions.Integer.Naive

Methods

(==) :: Partition -> Partition -> Bool

(/=) :: Partition -> Partition -> Bool

Ord Partition

Defined in Math.Combinat.Partitions.Integer.Naive

Methods

compare :: Partition -> Partition -> Ordering

(<) :: Partition -> Partition -> Bool

(<=) :: Partition -> Partition -> Bool

(>) :: Partition -> Partition -> Bool

(>=) :: Partition -> Partition -> Bool

max :: Partition -> Partition -> Partition

min :: Partition -> Partition -> Partition

Read Partition

Defined in Math.Combinat.Partitions.Integer.Naive

Methods

readsPrec :: Int -> ReadS Partition

readList :: ReadS [Partition]

readPrec :: ReadPrec Partition

readListPrec :: ReadPrec [Partition]

Show Partition

Defined in Math.Combinat.Partitions.Integer.Naive

Methods

showsPrec :: Int -> Partition -> ShowS

show :: Partition -> String

showList :: [Partition] -> ShowS

HasDuality Partition

Defined in Math.Combinat.Partitions.Integer.Naive

Methods

dual :: Partition -> Partition

HasWeight Partition

Defined in Math.Combinat.Partitions.Integer.Naive

Methods

weight :: Partition -> Int

HasHeight Partition

Defined in Math.Combinat.Partitions.Integer.Naive

Methods

height :: Partition -> Int

HasWidth Partition

Defined in Math.Combinat.Partitions.Integer.Naive

Methods

width :: Partition -> Int

HasNumberOfParts Partition

Defined in Math.Combinat.Partitions.Integer.Naive

Methods

numberOfParts :: Partition -> Int

CanBeEmpty Partition

Defined in Math.Combinat.Partitions.Integer.Naive

Methods

isEmpty :: Partition -> Bool

empty :: Partition

DrawASCII Partition

Defined in Math.Combinat.Partitions.Integer

Methods

ascii :: Partition -> ASCII

HasShape (Tableau a) Partition

Defined in Math.Combinat.Tableaux

Methods

shape :: Tableau a -> Partition

Conversion to/from lists

fromPartition :: Partition -> [Int]

mkPartition :: [Int] -> Partition

Sorts the input, and cuts the nonpositive elements.

toPartition :: [Int] -> Partition

Checks whether the input is an integer partition. See the note at isPartition!

toPartitionUnsafe :: [Int] -> Partition

Assumes that the input is decreasing.

isPartition :: [Int] -> Bool

This returns True if the input is non-increasing sequence of positive integers (possibly empty); False otherwise.

Conversion to/from exponent vectors

toExponentVector :: Partition -> [Int]

Converts a partition to an exponent vector.

For example,

toExponentVector (Partition [4,4,2,2,2,1]) == [1,3,0,2]

meaning (1^1,2^3,3^0,4^2).

fromExponentVector :: [Int] -> Partition

dropTailingZeros :: [Int] -> [Int]

Union and sum

unionOfPartitions :: Partition -> Partition -> Partition

This is simply the union of parts. For example

Partition [4,2,1] `unionOfPartitions` Partition [4,3,1] == Partition [4,4,3,2,1,1]

Note: This is the dual of pointwise sum, sumOfPartitions

sumOfPartitions :: Partition -> Partition -> Partition

Pointwise sum of the parts. For example:

Partition [3,2,1,1] `sumOfPartitions` Partition [4,3,1] == Partition [7,5,2,1]

Note: This is the dual of unionOfPartitions

Generating partitions

partitions :: Int -> [Partition]

Partitions of d.

partitions'

Arguments

:: (Int, Int)

(height,width)

-> Int

d

-> [Partition]

Partitions of d, fitting into a given rectangle. The order is again lexicographic.

allPartitions :: Int -> [Partition]

All integer partitions up to a given degree (that is, all integer partitions whose sum is less or equal to d)

allPartitionsGrouped :: Int -> [[Partition]]

All integer partitions up to a given degree (that is, all integer partitions whose sum is less or equal to d), grouped by weight

allPartitions'

Arguments

:: (Int, Int)

(height,width)

-> [Partition]

All integer partitions fitting into a given rectangle.

allPartitionsGrouped'

Arguments

:: (Int, Int)

(height,width)

-> [[Partition]]

All integer partitions fitting into a given rectangle, grouped by weight.

Counting partitions

countPartitions :: Int -> Integer

Number of partitions of n (looking up a table built using Euler's algorithm)

countPartitions' :: (Int, Int) -> Int -> Integer

Number of of d, fitting into a given rectangle. Naive recursive algorithm.

countAllPartitions :: Int -> Integer

countAllPartitions' :: (Int, Int) -> Integer

Count all partitions fitting into a rectangle. # = \binom { h+w } { h }

countPartitionsWithKParts

Arguments

:: Int

k = number of parts

-> Int

n = the integer we partition

-> Integer

Count partitions of n into k parts.

Naive recursive algorithm.

Random partitions

randomPartition :: RandomGen g => Int -> g -> (Partition, g)

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 of partitions counts 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

randomPartitions

Arguments

:: forall g. 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.

Dominating / dominated partitions

dominanceCompare :: Partition -> Partition -> Maybe Ordering

Dominance partial ordering as a partial ordering.

dominatedPartitions :: Partition -> [Partition]

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 :: Partition -> [Partition]

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 ]

Conjugate lexicographic ordering

conjugateLexicographicCompare :: Partition -> Partition -> Ordering

newtype ConjLex

Constructors

ConjLex Partition

Instances

Eq ConjLex

Defined in Math.Combinat.Partitions.Integer

Methods

(==) :: ConjLex -> ConjLex -> Bool

(/=) :: ConjLex -> ConjLex -> Bool

Ord ConjLex

Defined in Math.Combinat.Partitions.Integer

Methods

compare :: ConjLex -> ConjLex -> Ordering

(<) :: ConjLex -> ConjLex -> Bool

(<=) :: ConjLex -> ConjLex -> Bool

(>) :: ConjLex -> ConjLex -> Bool

(>=) :: ConjLex -> ConjLex -> Bool

max :: ConjLex -> ConjLex -> ConjLex

min :: ConjLex -> ConjLex -> ConjLex

Show ConjLex

Defined in Math.Combinat.Partitions.Integer

Methods

showsPrec :: Int -> ConjLex -> ShowS

show :: ConjLex -> String

showList :: [ConjLex] -> ShowS

fromConjLex :: ConjLex -> Partition

Partitions with given number of parts

partitionsWithKParts

Arguments

:: Int

k = number of parts

-> Int

n = the integer we partition

-> [Partition]

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]

Partitions of n with only odd parts

partitionsWithDistinctParts :: Int -> [Partition]

Partitions of n with distinct parts.

Note:

length (partitionsWithDistinctParts d) == length (partitionsWithOddParts d)

Sub- and super-partitions of a given partition

subPartitions :: Int -> Partition -> [Partition]

Sub-partitions of a given partition with the given weight:

sort (subPartitions d q) == sort [ p | p <- partitions d, isSubPartitionOf p q ]

allSubPartitions :: Partition -> [Partition]

All sub-partitions of a given partition

superPartitions :: Int -> Partition -> [Partition]

Super-partitions of a given partition with the given weight:

sort (superPartitions d p) == sort [ q | q <- partitions d, isSubPartitionOf p q ]

ASCII Ferrers diagrams

data PartitionConvention

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:

 @
 @@@@
 @@@@@

Constructors

EnglishNotation

English notation

EnglishNotationCCW

English notation rotated by 90 degrees counterclockwise

FrenchNotation

French notation (mirror of English notation to the x axis)

Instances

Eq PartitionConvention

Defined in Math.Combinat.Partitions.Integer

Methods

(==) :: PartitionConvention -> PartitionConvention -> Bool

(/=) :: PartitionConvention -> PartitionConvention -> Bool

Show PartitionConvention

Defined in Math.Combinat.Partitions.Integer

Methods

showsPrec :: Int -> PartitionConvention -> ShowS

show :: PartitionConvention -> String

showList :: [PartitionConvention] -> ShowS

asciiFerrersDiagram :: Partition -> ASCII

Synonym for asciiFerrersDiagram' EnglishNotation '@'

Try for example:

autoTabulate RowMajor (Right 8) (map asciiFerrersDiagram $ partitions 9)

asciiFerrersDiagram' :: PartitionConvention -> Char -> Partition -> ASCII

Orphan instances

DrawASCII Partition

Methods

ascii :: Partition -> ASCII