combinat-0.2.9.0: Generate and manipulate various combinatorial objects.

Safe HaskellNone
LanguageHaskell2010

Math.Combinat.Partitions.Integer.Naive

Contents

Description

Naive implementation of partitions of integers, encoded as list of Int-s.

Integer partitions are nonincreasing sequences of positive integers.

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

Synopsis

Type and basic stuff

newtype Partition Source #

A partition of an integer. The additional invariant enforced here is that partitions are monotone decreasing sequences of positive integers. The Ord instance is lexicographical.

Constructors

Partition [Int] 
Instances
Eq Partition Source # 
Instance details

Defined in Math.Combinat.Partitions.Integer.Naive

Ord Partition Source # 
Instance details

Defined in Math.Combinat.Partitions.Integer.Naive

Read Partition Source # 
Instance details

Defined in Math.Combinat.Partitions.Integer.Naive

Show Partition Source # 
Instance details

Defined in Math.Combinat.Partitions.Integer.Naive

HasDuality Partition Source # 
Instance details

Defined in Math.Combinat.Partitions.Integer.Naive

HasWeight Partition Source # 
Instance details

Defined in Math.Combinat.Partitions.Integer.Naive

Methods

weight :: Partition -> Int Source #

HasHeight Partition Source # 
Instance details

Defined in Math.Combinat.Partitions.Integer.Naive

Methods

height :: Partition -> Int Source #

HasWidth Partition Source # 
Instance details

Defined in Math.Combinat.Partitions.Integer.Naive

Methods

width :: Partition -> Int Source #

HasNumberOfParts Partition Source # 
Instance details

Defined in Math.Combinat.Partitions.Integer.Naive

CanBeEmpty Partition Source # 
Instance details

Defined in Math.Combinat.Partitions.Integer.Naive

DrawASCII Partition Source # 
Instance details

Defined in Math.Combinat.Partitions.Integer

HasShape (Tableau a) Partition Source # 
Instance details

Defined in Math.Combinat.Tableaux

Methods

shape :: Tableau a -> Partition Source #

partitionHeight :: Partition -> Int Source #

The first element of the sequence.

partitionWidth :: Partition -> Int Source #

The length of the sequence (that is, the number of parts).

partitionWeight :: Partition -> Int Source #

The weight of the partition (that is, the sum of the corresponding sequence).

dualPartition :: Partition -> Partition Source #

The dual (or conjugate) partition.

elements :: Partition -> [(Int, Int)] Source #

Example:

elements (toPartition [5,4,1]) ==
  [ (1,1), (1,2), (1,3), (1,4), (1,5)
  , (2,1), (2,2), (2,3), (2,4)
  , (3,1)
  ]

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 #

Exponential form

toExponentialForm :: Partition -> [(Int, Int)] Source #

We convert a partition to exponential form. (i,e) mean (i^e); for example [(1,4),(2,3)] corresponds to (1^4)(2^3) = [2,2,2,1,1,1,1]. Another example:

toExponentialForm (Partition [5,5,3,2,2,2,2,1,1]) == [(1,2),(2,4),(3,1),(5,2)]

List-like operations

diffSequence :: Partition -> [Int] Source #

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

Dominance order

dominates :: Partition -> Partition -> Bool Source #

q `dominates` p returns True if q >= p in the dominance order of partitions (this is partial ordering on the set of partitions of n).

See http://en.wikipedia.org/wiki/Dominance_order

Containment partial ordering

isSubPartitionOf :: Partition -> Partition -> Bool Source #

Returns True of the first partition is a subpartition (that is, fit inside) of the second. This includes equality

isSuperPartitionOf :: Partition -> Partition -> Bool Source #

This is provided for convenience/completeness only, as:

isSuperPartitionOf q p == isSubPartitionOf p q

The Pieri rule

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

The Pieri rule computes s[lambda]*h[n] as a sum of s[mu]-s (each with coefficient 1).

See for example http://en.wikipedia.org/wiki/Pieri's_formula

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

The dual Pieri rule computes s[lambda]*e[n] as a sum of s[mu]-s (each with coefficient 1)