combinat-0.2.10.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.

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

Synopsis

# The compact partition data type

newtype Partition Source #

Constructors

 Partition WordVec

#### Instances

Instances details
 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 #

# 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!

# Partial orderings

q dominates p

# Pieri rule

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 #