-- | Skew partitions.
--
-- Skew partitions are the difference of two integer partitions, denoted by @lambda/mu@.
--
-- For example
--
-- > mkSkewPartition (Partition [9,7,3,2,2,1] , Partition [5,3,2,1])
--
-- creates the skew partition @(9,7,3,2,2,1) / (5,3,2,1)@, which looks like
--
-- <<svg/skew3.svg>>
--

{-# LANGUAGE CPP, BangPatterns #-}
module Math.Combinat.Partitions.Skew where

--------------------------------------------------------------------------------

import Data.List

import Math.Combinat.Classes
import Math.Combinat.Partitions.Integer
import Math.Combinat.ASCII

--------------------------------------------------------------------------------
-- * Basics

-- | A skew partition @lambda/mu@ is internally represented by the list @[ (mu_i , lambda_i-mu_i) | i<-[1..n] ]@
newtype SkewPartition = SkewPartition [(Int,Int)] deriving (SkewPartition -> SkewPartition -> Bool
(SkewPartition -> SkewPartition -> Bool)
-> (SkewPartition -> SkewPartition -> Bool) -> Eq SkewPartition
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: SkewPartition -> SkewPartition -> Bool
$c/= :: SkewPartition -> SkewPartition -> Bool
== :: SkewPartition -> SkewPartition -> Bool
$c== :: SkewPartition -> SkewPartition -> Bool
Eq,Eq SkewPartition
Eq SkewPartition
-> (SkewPartition -> SkewPartition -> Ordering)
-> (SkewPartition -> SkewPartition -> Bool)
-> (SkewPartition -> SkewPartition -> Bool)
-> (SkewPartition -> SkewPartition -> Bool)
-> (SkewPartition -> SkewPartition -> Bool)
-> (SkewPartition -> SkewPartition -> SkewPartition)
-> (SkewPartition -> SkewPartition -> SkewPartition)
-> Ord SkewPartition
SkewPartition -> SkewPartition -> Bool
SkewPartition -> SkewPartition -> Ordering
SkewPartition -> SkewPartition -> SkewPartition
forall a.
Eq a
-> (a -> a -> Ordering)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> a)
-> (a -> a -> a)
-> Ord a
min :: SkewPartition -> SkewPartition -> SkewPartition
$cmin :: SkewPartition -> SkewPartition -> SkewPartition
max :: SkewPartition -> SkewPartition -> SkewPartition
$cmax :: SkewPartition -> SkewPartition -> SkewPartition
>= :: SkewPartition -> SkewPartition -> Bool
$c>= :: SkewPartition -> SkewPartition -> Bool
> :: SkewPartition -> SkewPartition -> Bool
$c> :: SkewPartition -> SkewPartition -> Bool
<= :: SkewPartition -> SkewPartition -> Bool
$c<= :: SkewPartition -> SkewPartition -> Bool
< :: SkewPartition -> SkewPartition -> Bool
$c< :: SkewPartition -> SkewPartition -> Bool
compare :: SkewPartition -> SkewPartition -> Ordering
$ccompare :: SkewPartition -> SkewPartition -> Ordering
$cp1Ord :: Eq SkewPartition
Ord,Int -> SkewPartition -> ShowS
[SkewPartition] -> ShowS
SkewPartition -> String
(Int -> SkewPartition -> ShowS)
-> (SkewPartition -> String)
-> ([SkewPartition] -> ShowS)
-> Show SkewPartition
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [SkewPartition] -> ShowS
$cshowList :: [SkewPartition] -> ShowS
show :: SkewPartition -> String
$cshow :: SkewPartition -> String
showsPrec :: Int -> SkewPartition -> ShowS
$cshowsPrec :: Int -> SkewPartition -> ShowS
Show)

-- | @mkSkewPartition (lambda,mu)@ creates the skew partition @lambda/mu@.
-- Throws an error if @mu@ is not a sub-partition of @lambda@.
mkSkewPartition :: (Partition,Partition) -> SkewPartition
mkSkewPartition :: (Partition, Partition) -> SkewPartition
mkSkewPartition ( lam :: Partition
lam@(Partition [Int]
bs) , mu :: Partition
mu@(Partition [Int]
as)) = if Partition
mu Partition -> Partition -> Bool
`isSubPartitionOf` Partition
lam 
  then [(Int, Int)] -> SkewPartition
SkewPartition ([(Int, Int)] -> SkewPartition) -> [(Int, Int)] -> SkewPartition
forall a b. (a -> b) -> a -> b
$ (Int -> Int -> (Int, Int)) -> [Int] -> [Int] -> [(Int, Int)]
forall a b c. (a -> b -> c) -> [a] -> [b] -> [c]
zipWith (\Int
b Int
a -> (Int
a,Int
bInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
a)) [Int]
bs ([Int]
as [Int] -> [Int] -> [Int]
forall a. [a] -> [a] -> [a]
++ Int -> [Int]
forall a. a -> [a]
repeat Int
0)
  else String -> SkewPartition
forall a. HasCallStack => String -> a
error String
"mkSkewPartition: mu should be a subpartition of lambda!" 

-- | Returns 'Nothing' if @mu@ is not a sub-partition of @lambda@.
safeSkewPartition :: (Partition,Partition) -> Maybe SkewPartition
safeSkewPartition :: (Partition, Partition) -> Maybe SkewPartition
safeSkewPartition ( lam :: Partition
lam@(Partition [Int]
bs) , mu :: Partition
mu@(Partition [Int]
as)) = if Partition
mu Partition -> Partition -> Bool
`isSubPartitionOf` Partition
lam 
  then SkewPartition -> Maybe SkewPartition
forall a. a -> Maybe a
Just (SkewPartition -> Maybe SkewPartition)
-> SkewPartition -> Maybe SkewPartition
forall a b. (a -> b) -> a -> b
$ [(Int, Int)] -> SkewPartition
SkewPartition ([(Int, Int)] -> SkewPartition) -> [(Int, Int)] -> SkewPartition
forall a b. (a -> b) -> a -> b
$ (Int -> Int -> (Int, Int)) -> [Int] -> [Int] -> [(Int, Int)]
forall a b c. (a -> b -> c) -> [a] -> [b] -> [c]
zipWith (\Int
b Int
a -> (Int
a,Int
bInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
a)) [Int]
bs ([Int]
as [Int] -> [Int] -> [Int]
forall a. [a] -> [a] -> [a]
++ Int -> [Int]
forall a. a -> [a]
repeat Int
0)
  else Maybe SkewPartition
forall a. Maybe a
Nothing

-- | The weight of a skew partition is the weight of the outer partition minus the
-- the weight of the inner partition (that is, the number of boxes present).
skewPartitionWeight :: SkewPartition -> Int
skewPartitionWeight :: SkewPartition -> Int
skewPartitionWeight (SkewPartition [(Int, Int)]
abs) = (Int -> Int -> Int) -> Int -> [Int] -> Int
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' Int -> Int -> Int
forall a. Num a => a -> a -> a
(+) Int
0 (((Int, Int) -> Int) -> [(Int, Int)] -> [Int]
forall a b. (a -> b) -> [a] -> [b]
map (Int, Int) -> Int
forall a b. (a, b) -> b
snd [(Int, Int)]
abs)

instance HasWeight SkewPartition where
  weight :: SkewPartition -> Int
weight = SkewPartition -> Int
skewPartitionWeight

-- | This function \"cuts off\" the \"uninteresting parts\" of a skew partition
normalizeSkewPartition :: SkewPartition -> SkewPartition
normalizeSkewPartition :: SkewPartition -> SkewPartition
normalizeSkewPartition (SkewPartition [(Int, Int)]
abs) = [(Int, Int)] -> SkewPartition
SkewPartition [(Int, Int)]
abs' where
  ([Int]
as,[Int]
bs) = [(Int, Int)] -> ([Int], [Int])
forall a b. [(a, b)] -> ([a], [b])
unzip [(Int, Int)]
abs
  a0 :: Int
a0 = [Int] -> Int
forall (t :: * -> *) a. (Foldable t, Ord a) => t a -> a
minimum [Int]
as
  k :: Int
k  = [Int] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length ((Int -> Bool) -> [Int] -> [Int]
forall a. (a -> Bool) -> [a] -> [a]
takeWhile (Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
==Int
0) [Int]
bs)
  abs' :: [(Int, Int)]
abs' = [Int] -> [Int] -> [(Int, Int)]
forall a b. [a] -> [b] -> [(a, b)]
zip [ Int
aInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
a0 | Int
a <- Int -> [Int] -> [Int]
forall a. Int -> [a] -> [a]
drop Int
k [Int]
as ] (Int -> [Int] -> [Int]
forall a. Int -> [a] -> [a]
drop Int
k [Int]
bs)
   
-- | Returns the outer and inner partition of a skew partition, respectively:
--
-- > mkSkewPartition . fromSkewPartition == id
--
fromSkewPartition :: SkewPartition -> (Partition,Partition)
fromSkewPartition :: SkewPartition -> (Partition, Partition)
fromSkewPartition (SkewPartition [(Int, Int)]
list) = ([Int] -> Partition
toPartition ((Int -> Int -> Int) -> [Int] -> [Int] -> [Int]
forall a b c. (a -> b -> c) -> [a] -> [b] -> [c]
zipWith Int -> Int -> Int
forall a. Num a => a -> a -> a
(+) [Int]
as [Int]
bs) , [Int] -> Partition
toPartition ((Int -> Bool) -> [Int] -> [Int]
forall a. (a -> Bool) -> [a] -> [a]
filter (Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>Int
0) [Int]
as)) where
  ([Int]
as,[Int]
bs) = [(Int, Int)] -> ([Int], [Int])
forall a b. [(a, b)] -> ([a], [b])
unzip [(Int, Int)]
list

-- | The @lambda@ part of @lambda/mu@
outerPartition :: SkewPartition -> Partition  
outerPartition :: SkewPartition -> Partition
outerPartition = (Partition, Partition) -> Partition
forall a b. (a, b) -> a
fst ((Partition, Partition) -> Partition)
-> (SkewPartition -> (Partition, Partition))
-> SkewPartition
-> Partition
forall b c a. (b -> c) -> (a -> b) -> a -> c
. SkewPartition -> (Partition, Partition)
fromSkewPartition 

-- | The @mu@ part of @lambda/mu@
innerPartition :: SkewPartition -> Partition  
innerPartition :: SkewPartition -> Partition
innerPartition = (Partition, Partition) -> Partition
forall a b. (a, b) -> b
snd ((Partition, Partition) -> Partition)
-> (SkewPartition -> (Partition, Partition))
-> SkewPartition
-> Partition
forall b c a. (b -> c) -> (a -> b) -> a -> c
. SkewPartition -> (Partition, Partition)
fromSkewPartition 

-- | The dual skew partition (that is, the mirror image to the main diagonal)
dualSkewPartition :: SkewPartition -> SkewPartition
dualSkewPartition :: SkewPartition -> SkewPartition
dualSkewPartition = (Partition, Partition) -> SkewPartition
mkSkewPartition ((Partition, Partition) -> SkewPartition)
-> (SkewPartition -> (Partition, Partition))
-> SkewPartition
-> SkewPartition
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Partition, Partition) -> (Partition, Partition)
f ((Partition, Partition) -> (Partition, Partition))
-> (SkewPartition -> (Partition, Partition))
-> SkewPartition
-> (Partition, Partition)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. SkewPartition -> (Partition, Partition)
fromSkewPartition where
  f :: (Partition, Partition) -> (Partition, Partition)
f (Partition
lam,Partition
mu) = (Partition -> Partition
dualPartition Partition
lam, Partition -> Partition
dualPartition Partition
mu)

instance HasDuality SkewPartition where
  dual :: SkewPartition -> SkewPartition
dual = SkewPartition -> SkewPartition
dualSkewPartition

-- | See "partitionElements"
skewPartitionElements :: SkewPartition -> [(Int, Int)]
skewPartitionElements :: SkewPartition -> [(Int, Int)]
skewPartitionElements (SkewPartition [(Int, Int)]
abs) = [[(Int, Int)]] -> [(Int, Int)]
forall (t :: * -> *) a. Foldable t => t [a] -> [a]
concat
  [ [ (Int
i,Int
j) | Int
j <- [Int
aInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
1 .. Int
aInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
b] ]
  | (Int
i,(Int
a,Int
b)) <- [Int] -> [(Int, Int)] -> [(Int, (Int, Int))]
forall a b. [a] -> [b] -> [(a, b)]
zip [Int
1..] [(Int, Int)]
abs
  ]

--------------------------------------------------------------------------------
-- * Listing skew partitions

-- | Lists all skew partitions with the given outer shape and given (skew) weight
skewPartitionsWithOuterShape :: Partition -> Int -> [SkewPartition]
skewPartitionsWithOuterShape :: Partition -> Int -> [SkewPartition]
skewPartitionsWithOuterShape Partition
outer Int
skewWeight 
  | Int
innerWeight Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
0 Bool -> Bool -> Bool
|| Int
innerWeight Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
outerWeight = []
  | Bool
otherwise = [ (Partition, Partition) -> SkewPartition
mkSkewPartition (Partition
outer,Partition
inner) | Partition
inner <- Int -> Partition -> [Partition]
subPartitions Int
innerWeight Partition
outer ]
  where
    outerWeight :: Int
outerWeight = Partition -> Int
forall a. HasWeight a => a -> Int
weight Partition
outer
    innerWeight :: Int
innerWeight = Int
outerWeight Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
skewWeight 

-- | Lists all skew partitions with the given outer shape and any (skew) weight
allSkewPartitionsWithOuterShape :: Partition -> [SkewPartition]
allSkewPartitionsWithOuterShape :: Partition -> [SkewPartition]
allSkewPartitionsWithOuterShape Partition
outer 
  = [[SkewPartition]] -> [SkewPartition]
forall (t :: * -> *) a. Foldable t => t [a] -> [a]
concat [ Partition -> Int -> [SkewPartition]
skewPartitionsWithOuterShape Partition
outer Int
w | Int
w<-[Int
0..Int
outerWeight] ]
  where
    outerWeight :: Int
outerWeight = Partition -> Int
forall a. HasWeight a => a -> Int
weight Partition
outer

-- | Lists all skew partitions with the given inner shape and given (skew) weight
skewPartitionsWithInnerShape :: Partition -> Int -> [SkewPartition]
skewPartitionsWithInnerShape :: Partition -> Int -> [SkewPartition]
skewPartitionsWithInnerShape Partition
inner Int
skewWeight 
  | Int
innerWeight Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
outerWeight = []
  | Bool
otherwise = [ (Partition, Partition) -> SkewPartition
mkSkewPartition (Partition
outer,Partition
inner) | Partition
outer <- Int -> Partition -> [Partition]
superPartitions Int
outerWeight Partition
inner ]
  where
    outerWeight :: Int
outerWeight = Int
innerWeight Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
skewWeight 
    innerWeight :: Int
innerWeight = Partition -> Int
forall a. HasWeight a => a -> Int
weight Partition
inner 

--------------------------------------------------------------------------------
-- connected components

{-
connectedComponents :: SkewPartition -> [((Int,Int),SkewPartition)]
connectedComponents = error "connectedComponents: not implemented yet"

isConnectedSkewPartition :: SkewPartition -> Bool
isConnectedSkewPartition skewp = length (connectedComponents skewp) == 1
-}

--------------------------------------------------------------------------------
-- * ASCII

asciiSkewFerrersDiagram :: SkewPartition -> ASCII
asciiSkewFerrersDiagram :: SkewPartition -> ASCII
asciiSkewFerrersDiagram = (Char, Char) -> PartitionConvention -> SkewPartition -> ASCII
asciiSkewFerrersDiagram' (Char
'@',Char
'.') PartitionConvention
EnglishNotation

asciiSkewFerrersDiagram' 
  :: (Char,Char)       
  -> PartitionConvention -- Orientation
  -> SkewPartition 
  -> ASCII
asciiSkewFerrersDiagram' :: (Char, Char) -> PartitionConvention -> SkewPartition -> ASCII
asciiSkewFerrersDiagram' (Char
outer,Char
inner) PartitionConvention
orient (SkewPartition [(Int, Int)]
abs) = [String] -> ASCII
asciiFromLines [String]
stuff where
  stuff :: [String]
stuff = case PartitionConvention
orient of
    PartitionConvention
EnglishNotation    -> [String]
ls
    PartitionConvention
EnglishNotationCCW -> [String] -> [String]
forall a. [a] -> [a]
reverse ([String] -> [String]
forall a. [[a]] -> [[a]]
transpose [String]
ls)
    PartitionConvention
FrenchNotation     -> [String] -> [String]
forall a. [a] -> [a]
reverse [String]
ls
  ls :: [String]
ls = [ Int -> Char -> String
forall a. Int -> a -> [a]
replicate Int
a Char
inner String -> ShowS
forall a. [a] -> [a] -> [a]
++ Int -> Char -> String
forall a. Int -> a -> [a]
replicate Int
b Char
outer | (Int
a,Int
b) <- [(Int, Int)]
abs ]

instance DrawASCII SkewPartition where
  ascii :: SkewPartition -> ASCII
ascii = SkewPartition -> ASCII
asciiSkewFerrersDiagram     

--------------------------------------------------------------------------------