combinat- Generate and manipulate various combinatorial objects.

Safe HaskellNone




Compact representation of integer partitions.

Partitions are conceptually nonincreasing sequences of positive integers.

When the partition fits into a 15x15 rectangle, we encode the parts as nibbles in a single 64-bit word. The most significant nibble is the first element, and the least significant nibble is used to encode the length. This way equality and comparison of 64-bit words is the same as the corresponding operations for partitions (lexicographic ordering).

This will make working with small partitions much more memory efficient (very helpful when building tables indexed by partitions, for example!) and hopefully quite a bit faster, too.

When they do not fit into a 15x15 rectangle, but fit into 255x7, 255x15, 255x23 or 255x31, respectively, then we extend the above to use the bytes of 1, 2, 3 or 4 64-bit words.

In the general case, we encode the partition as a list of 64-bit words, each encoding 4 16-bit parts.

Partitions with elements bigger than 65535 are not supported.

Note: This is an internal module, you are not supposed to import it directly.


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

cmp :: 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

pieriRuleSingleBox :: Partition -> [Partition] Source #

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

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 #

toOne :: Int -> [Int] Source #