combinat- Generate and manipulate various combinatorial objects.
Safe HaskellNone



Compact representation of integer partitions.

Partitions are conceptually nonincreasing sequences of positive integers.

This implementation uses the compact-word-vectors library internally to provide a much more memory-efficient Partition type that the naive lists of integer. This is very helpful when building large tables indexed by partitions, for example; and hopefully quite a bit faster, too.

Note: This is an internal module, you are not supposed to import it directly. It is also not fully ready to be used yet...


The compact partition data type

Pattern synonyms

pattern Nil :: Partition Source #

Pattern sysnonyms allows us to use existing code with minimal modifications

pattern Cons :: Int -> Partition -> Partition Source #

pattern Partition_ :: [Int] -> Partition Source #

Simulated newtype constructor

pattern Head :: Int -> Partition Source #

pattern Length :: Int -> Partition Source #

Lexicographic comparison

cmpLexico :: Partition -> Partition -> Ordering Source #

The lexicographic ordering

Basic (de)constructrion

partitionTail :: Partition -> Partition Source #

partitionTail p == snd (uncons p)

cons :: Int -> Partition -> Partition Source #

We assume that x >= partitionHeight p!

snoc :: Partition -> Int -> Partition Source #

We assume that the element is not bigger than the last element!

exponential form

Width and height of the bounding rectangle

width :: Partition -> Int Source #

Width, or the number of parts

height :: Partition -> Int Source #

Height, or the first (that is, the largest) element

widthHeight :: Partition -> (Int, Int) Source #

Width and height

Differential sequence

diffSequence :: Partition -> [Int] Source #

From a non-increasing sequence [a1,a2,..,an] this computes the sequence of differences [a1-a2,a2-a3,...,an-0]

reverseDiffSequence :: Partition -> [Int] Source #

From a non-increasing sequence [a1,a2,..,an] this computes the reversed sequence of differences [ a[n]-0 , a[n-1]-a[n] , ... , a[2]-a[3] , a[1]-a[2] ]

Dual partition

Conversion to list

toDescList :: Partition -> [Int] Source #

returns a descending (non-increasing) list

toAscList :: Partition -> [Int] Source #

Returns a reversed (ascending; non-decreasing) list

Conversion from list

fromDescList' Source #


:: Int


-> [Int]

the list

-> Partition 

We assume that the input is a non-increasing list of positive integers!

Partial orderings

Pieri rule

pieriRule :: Partition -> Int -> [Partition] Source #

Expands to product s[lambda]*h[k] as a sum of s[mu]-s. See's_formula

local (internally used) utility functions

safeTail :: [Int] -> [Int] Source #