module Math.Combinat.Tableaux where
import Data.List
import Math.Combinat.Helper
import Math.Combinat.Numbers (factorial,binomial)
import Math.Combinat.Partitions
type Tableau a = [[a]]
_shape :: Tableau a -> [Int]
_shape t = map length t
shape :: Tableau a -> Partition
shape t = toPartition (_shape t)
dualTableau :: Tableau a -> Tableau a
dualTableau = transpose
content :: Tableau a -> [a]
content = concat
hooks :: Partition -> Tableau (Int,Int)
hooks part = zipWith f p [1..] where
p = fromPartition part
q = _dualPartition p
f l i = zipWith (\x y -> (xi+1,y)) q [l,l1..1]
hookLengths :: Partition -> Tableau Int
hookLengths part = (map . map) (\(i,j) -> i+j1) (hooks part)
rowWord :: Tableau a -> [a]
rowWord = concat . reverse
rowWordToTableau :: Ord a => [a] -> Tableau a
rowWordToTableau xs = reverse rows where
rows = break xs
break [] = [[]]
break [x] = [[x]]
break (x:xs@(y:_)) = if x>y
then [x] : break xs
else let (h:t) = break xs in (x:h):t
columnWord :: Tableau a -> [a]
columnWord = rowWord . transpose
columnWordToTableau :: Ord a => [a] -> Tableau a
columnWordToTableau = transpose . rowWordToTableau
standardYoungTableaux :: Partition -> [Tableau Int]
standardYoungTableaux shape' = map rev $ tableaux shape where
shape = fromPartition shape'
rev = reverse . map reverse
tableaux :: [Int] -> [Tableau Int]
tableaux p =
case p of
[] -> [[]]
[n] -> [[[n,n1..1]]]
_ -> worker (n,k) 0 [] p
where
n = sum p
k = length p
worker :: (Int,Int) -> Int -> [Int] -> [Int] -> [Tableau Int]
worker _ _ _ [] = []
worker nk i ls (x:rs) = case rs of
(y:_) -> if x==y
then worker nk (i+1) (x:ls) rs
else worker2 nk i ls x rs
[] -> worker2 nk i ls x rs
worker2 :: (Int,Int) -> Int -> [Int] -> Int -> [Int] -> [Tableau Int]
worker2 nk@(n,k) i ls x rs = new ++ worker nk (i+1) (x:ls) rs where
old = if x>1
then tableaux $ reverse ls ++ (x1) : rs
else map ([]:) $ tableaux $ reverse ls ++ rs
a = k1i
new =
map (f a) old
f :: Int -> Tableau Int -> Tableau Int
f _ [] = []
f 0 (t:ts) = (n:t) : f (1) ts
f j (t:ts) = t : f (j1) ts
countStandardYoungTableaux :: Partition -> Integer
countStandardYoungTableaux part =
factorial n `div` h where
h = product $ map fromIntegral $ concat $ hookLengths part
n = weight part
semiStandardYoungTableaux :: Int -> Partition -> [Tableau Int]
semiStandardYoungTableaux n part = worker (repeat 0) shape where
shape = fromPartition part
worker _ [] = [[]]
worker prevRow (s:ss)
= [ (r:rs) | r <- row n s 1 prevRow, rs <- worker (map (+1) r) ss ]
row :: Int -> Int -> Int -> [Int] -> [[Int]]
row _ 0 _ _ = [[]]
row n len prev (x:xs) = [ (a:as) | a <- [max x prev..n] , as <- row n (len1) a xs ]
countSemiStandardYoungTableaux :: Int -> Partition -> Integer
countSemiStandardYoungTableaux n shape = k `div` h where
h = product $ map fromIntegral $ concat $ hookLengths shape
k = product [ fromIntegral (n+ji) | (i,j) <- elements shape ]