Copyright	Anders Claesson 2013-2016
Maintainer	Anders Claesson <anders.claesson@gmail.com>
Safe Haskell	Safe-Inferred
Language	Haskell2010

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

type GeneralizedPerm = [(Int, Int)]
type Entry = Int
type SSYT = [[Entry]]
data SSYTPair = SSYTPair {
- insertionTableau :: SSYT
- recordingTableau :: SSYT
}
class Shape a where
- shape :: a -> [Int]
empty :: SSYTPair
null :: SSYTPair -> Bool
display :: SSYTPair -> String
fromPerm :: Perm -> SSYTPair
fromGeneralizedPerm :: GeneralizedPerm -> SSYTPair
toPerm :: SSYTPair -> Perm
toGeneralizedPerm :: SSYTPair -> GeneralizedPerm

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

Instances details

Show SSYTPair Source #
Instance details Defined in Sym.Perm.SSYT Methods showsPrec :: Int -> SSYTPair -> ShowS # show :: SSYTPair -> String # showList :: [SSYTPair] -> ShowS #
Eq SSYTPair Source #
Instance details Defined in Sym.Perm.SSYT Methods (==) :: SSYTPair -> SSYTPair -> Bool # (/=) :: SSYTPair -> SSYTPair -> Bool #
Permutation SSYTPair Source #
Instance details Defined in Sym Methods st :: SSYTPair -> Perm Source # act :: Perm -> SSYTPair -> SSYTPair Source # size :: SSYTPair -> Int Source # idperm :: Int -> SSYTPair Source # inverse :: SSYTPair -> SSYTPair Source # ordiso :: Perm -> SSYTPair -> Bool Source # unst :: Perm -> SSYTPair Source #
Shape SSYTPair Source #
Instance details Defined in Sym.Perm.SSYT Methods shape :: SSYTPair -> [Int] Source #

class Shape a where Source #

Methods

shape :: a -> [Int] Source #

Instances

Instances details

Shape SSYT Source #
Instance details Defined in Sym.Perm.SSYT Methods shape :: SSYT -> [Int] Source #
Shape SSYTPair Source #
Instance details Defined in Sym.Perm.SSYT Methods shape :: SSYTPair -> [Int] Source #

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.