Sym.Perm.SSYT

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.

Documentation

type GeneralizedPerm = [(Int, Int)]

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

type Entry = Int

An entry is a non-negative integer

type SSYT = [[Entry]]

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

data SSYTPair

A pair of Semistandard Young Tableaux.

Constructors

SSYTPair

Fields

• insertionTableau :: SSYT
• recordingTableau :: SSYT

Instances

Eq SSYTPair

Methods

(==) :: SSYTPair -> SSYTPair -> Bool

(/=) :: SSYTPair -> SSYTPair -> Bool

Show SSYTPair

Methods

showsPrec :: Int -> SSYTPair -> ShowS

show :: SSYTPair -> String

showList :: [SSYTPair] -> ShowS

Shape SSYTPair

Methods

shape :: SSYTPair -> [Int]

Permutation SSYTPair

Methods

st :: SSYTPair -> Perm

act :: Perm -> SSYTPair -> SSYTPair

size :: SSYTPair -> Int

idperm :: Int -> SSYTPair

inverse :: SSYTPair -> SSYTPair

ordiso :: Perm -> SSYTPair -> Bool

unst :: Perm -> SSYTPair

class Shape a where

Minimal complete definition

shape

Methods

shape :: a -> [Int]

Instances

Shape SSYTPair

Methods

shape :: SSYTPair -> [Int]

Shape SSYT

Methods

shape :: SSYT -> [Int]

empty :: SSYTPair

A pair of empty Young tableaux.

null :: SSYTPair -> Bool

Check if a given pair of Young tableaux are empty.

display :: SSYTPair -> String

Produce a string for pretty printing SSYT pairs.

fromPerm :: Perm -> SSYTPair

The Robinson-Schensted algorithm.

fromGeneralizedPerm :: GeneralizedPerm -> SSYTPair

The Robinson-Schensted-Knuth (RSK) algorithm.

toPerm :: SSYTPair -> Perm

The inverse of the Robinson-Schensted algorithm.

toGeneralizedPerm :: SSYTPair -> GeneralizedPerm

The inverse of the Robinson-Schensted-Knuth algorithm.