Copyright	Anders Claesson 2013
Maintainer	Anders Claesson <anders.claesson@gmail.com>
Safe Haskell	None
Language	Haskell98

Sym.Perm.SSYT

Description

Data types for Semistandard Young Tableaux (SSYT) and functions for converting between (generalized) permutataions and SSYT. In other words, this module implements the Robinson-Schensted-Knuth (RSK) correspondence.

Synopsis

Documentation

type GeneralizedPerm = [(Int, Int)] Source

A Generalized Permutation is a lexicographically sorted list of pairs of non-negative integers.

type Entry = Int Source

An entry is a non-negative integer

type SSYT = [[Entry]] Source

A Semistandard Young Tableau (SSYT): the entries weakly increase along each row and strictly increase down each column.

data SSYTPair Source

A pair of Semistandard Young Tableaux.

Constructors

SSYTPair
Fields insertionTableau :: SSYT recordingTableau :: SSYT

Instances

Eq SSYTPair
Show SSYTPair
Shape SSYTPair
Permutation SSYTPair

class Shape a where Source

Methods

shape :: a -> [Int] Source

Instances

Shape SSYTPair
Shape SSYT

empty :: SSYTPair Source

A pair of empty Young tableaux.

null :: SSYTPair -> Bool Source

Check if a given pair of Young tableaux are empty.

display :: SSYTPair -> String Source

Produce a string for pretty printing SSYT pairs.

fromPerm :: Perm -> SSYTPair Source

The Robinson-Schensted algorithm.

fromGeneralizedPerm :: GeneralizedPerm -> SSYTPair Source

The Robinson-Schensted-Knuth (RSK) algorithm.

toPerm :: SSYTPair -> Perm Source

The inverse of the Robinson-Schensted algorithm.

toGeneralizedPerm :: SSYTPair -> GeneralizedPerm Source

The inverse of the Robinson-Schensted-Knuth algorithm.