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

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