combinat-0.2.10.0: Generate and manipulate various combinatorial objects.
Safe HaskellNone
LanguageHaskell2010

Math.Combinat.Partitions.Skew.Ribbon

Description

Ribbons (also called border strips, skew hooks, skew rim hooks, etc...).

Ribbons are skew partitions that are 1) connected, 2) do not contain 2x2 blocks. Intuitively, they are 1-box wide continuous strips on the boundary.

An alternative definition that they are skew partitions whose projection to the diagonal line is a continuous segment of width 1.

Synopsis

Corners (TODO: move to Partitions - but we also want to refactor that)

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

The coordinates of the outer corners

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

The coordinates of the inner corners, including the two on the two coordinate axes. For the partition [5,4,1] the result should be [(0,5),(1,4),(2,1),(3,0)]

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

Sequence of all the (extended) corners

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

The inner corner boxes of the partition. Coordinates are counted from 1 (cf.the elements function), and the first coordinate is the row, the second the column (in English notation).

For the partition [5,4,1] the result should be [(1,4),(2,1)]

innerCornerBoxes lambda == (tail $ init $ extendedInnerCorners lambda)

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

The outer corner boxes of the partition. Coordinates are counted from 1 (cf.the elements function), and the first coordinate is the row, the second the column (in English notation).

For the partition [5,4,1] the result should be [(1,5),(2,4),(3,1)]

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

The outer and inner corner boxes interleaved, so together they form the turning points of the full border strip

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

Naive (and very slow) implementation of innerCornerBoxes, for testing purposes

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

Naive (and very slow) implementation of outerCornerBoxes, for testing purposes

Ribbon

isRibbon :: SkewPartition -> Bool Source #

A skew partition is a a ribbon (or border strip) if and only if projected to the diagonals the result is an interval.

data Ribbon Source #

Border strips (or ribbons) are defined to be skew partitions which are connected and do not contain 2x2 blocks.

The length of a border strip is the number of boxes it contains, and its height is defined to be one less than the number of rows (in English notation) it occupies. The width is defined symmetrically to be one less than the number of columns it occupies.

Constructors

Ribbon 

Instances

Instances details
Eq Ribbon Source # 
Instance details

Defined in Math.Combinat.Partitions.Skew.Ribbon

Methods

(==) :: Ribbon -> Ribbon -> Bool #

(/=) :: Ribbon -> Ribbon -> Bool #

Ord Ribbon Source # 
Instance details

Defined in Math.Combinat.Partitions.Skew.Ribbon

Show Ribbon Source # 
Instance details

Defined in Math.Combinat.Partitions.Skew.Ribbon

Inner border strips

innerRibbons :: Partition -> [Ribbon] Source #

Ribbons (or border strips) are defined to be skew partitions which are connected and do not contain 2x2 blocks. This function returns the border strips whose outer partition is the given one.

innerRibbonsOfLength :: Partition -> Int -> [Ribbon] Source #

Inner border strips (or ribbons) of the given length

Outer border strips

listHooks :: Int -> [Partition] Source #

Hooks of length n (TODO: move to the partition module)

outerRibbonsOfLength :: Partition -> Int -> [Ribbon] Source #

Outer border strips (or ribbons) of the given length

Naive implementations (for testing)

innerRibbonsNaive :: Partition -> [Ribbon] Source #

Naive (and slow) implementation listing all inner border strips

innerRibbonsOfLengthNaive :: Partition -> Int -> [Ribbon] Source #

Naive (and slow) implementation listing all inner border strips of the given length

outerRibbonsOfLengthNaive :: Partition -> Int -> [Ribbon] Source #

Naive (and slow) implementation listing all outer border strips of the given length

Annotated borders

data BorderBox Source #

A box on the border of a partition

Constructors

BorderBox 

Instances

Instances details
Show BorderBox Source # 
Instance details

Defined in Math.Combinat.Partitions.Skew.Ribbon

annotatedInnerBorderStrip :: Partition -> [BorderBox] Source #

The boxes of the full inner border strip, annotated with whether a border strip can start or end there.

annotatedOuterBorderStrip :: Partition -> [BorderBox] Source #

The boxes of the full outer border strip, annotated with whether a border strip can start or end there.