combinat-0.2.9.0: Generate and manipulate various combinatorial objects.

Math.Combinat.Partitions.Integer.Compact

Description

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.

Synopsis

# The compact partition data type

data Partition Source #

Constructors

 Nibble !Word64 Medium1 !Word64 Medium2 !Word64 !Word64 Medium3 !Word64 !Word64 !Word64 Medium4 !Word64 !Word64 !Word64 !Word64 WordList !Int ![Word64]
Instances
 Source # Instance detailsDefined in Math.Combinat.Partitions.Integer.Compact Methods Source # Instance detailsDefined in Math.Combinat.Partitions.Integer.Compact Methods Source # Instance detailsDefined in Math.Combinat.Partitions.Integer.Compact MethodsshowList :: [Partition] -> ShowS #

for debugging

# 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

The lexicographic ordering

# Basic (de)constructrion

partitionTail p == snd (uncons p)

We assume that x >= partitionHeight p!

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

# Width and height of the bounding rectangle

Width, or the number of parts

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

Width and height

# Differential sequence

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

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] ]

# Conversion to list

returns a descending (non-increasing) list

toAscList :: Partition -> [Int] Source #

Returns a reversed (ascending; non-decreasing) list

# Conversion from list

Arguments

 :: Int length -> [Int] the list -> Partition

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

# Pieri rule

Expands to product s[lambda]*h[1] = s[lambda]*e[1] as a sum of s[mu]-s. See https://en.wikipedia.org/wiki/Pieri's_formula

Expands to product s[lambda]*h[k] as a sum of s[mu]-s. See https://en.wikipedia.org/wiki/Pieri's_formula

# local (internally used) utility functions

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

toOne :: Int -> [Int] Source #