-- | Partition functions working on lists of integers.
-- 
-- It's not recommended to use this module directly.

{-# LANGUAGE CPP, BangPatterns, ScopedTypeVariables #-}
module Math.Combinat.Partitions.Integer.IntList where

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

import Data.List
import Control.Monad ( liftM , replicateM )

import Math.Combinat.Numbers ( factorial , binomial , multinomial )
import Math.Combinat.Helper

import Data.Array
import System.Random

import Math.Combinat.Partitions.Integer.Count ( countPartitions )

--------------------------------------------------------------------------------
-- * Type and basic stuff

-- | Sorts the input, and cuts the nonpositive elements.
_mkPartition :: [Int] -> [Int]
_mkPartition :: [Int] -> [Int]
_mkPartition [Int]
xs = (Int -> Int -> Ordering) -> [Int] -> [Int]
forall a. (a -> a -> Ordering) -> [a] -> [a]
sortBy (Int -> Int -> Ordering
forall a. Ord a => a -> a -> Ordering
reverseCompare) ([Int] -> [Int]) -> [Int] -> [Int]
forall a b. (a -> b) -> a -> b
$ (Int -> Bool) -> [Int] -> [Int]
forall a. (a -> Bool) -> [a] -> [a]
filter (Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>Int
0) [Int]
xs
 
-- | This returns @True@ if the input is non-increasing sequence of 
-- /positive/ integers (possibly empty); @False@ otherwise.
--
_isPartition :: [Int] -> Bool
_isPartition :: [Int] -> Bool
_isPartition []  = Bool
True
_isPartition [Int
x] = Int
x Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
0
_isPartition (Int
x:xs :: [Int]
xs@(Int
y:[Int]
_)) = (Int
x Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Int
y) Bool -> Bool -> Bool
&& [Int] -> Bool
_isPartition [Int]
xs


_dualPartition :: [Int] -> [Int]
_dualPartition :: [Int] -> [Int]
_dualPartition [] = []
_dualPartition [Int]
xs = Int -> [Int] -> [Int] -> [Int]
forall t. Num t => t -> [Int] -> [Int] -> [t]
go Int
0 ([Int] -> [Int]
_diffSequence [Int]
xs) [] where
  go :: t -> [Int] -> [Int] -> [t]
go !t
i (Int
d:[Int]
ds) [Int]
acc = t -> [Int] -> [Int] -> [t]
go (t
it -> t -> t
forall a. Num a => a -> a -> a
+t
1) [Int]
ds (Int
dInt -> [Int] -> [Int]
forall a. a -> [a] -> [a]
:[Int]
acc)
  go t
n  []     [Int]
acc = t -> [Int] -> [t]
forall t. Num t => t -> [Int] -> [t]
finish t
n [Int]
acc 
  finish :: t -> [Int] -> [t]
finish !t
j (Int
k:[Int]
ks) = Int -> t -> [t]
forall a. Int -> a -> [a]
replicate Int
k t
j [t] -> [t] -> [t]
forall a. [a] -> [a] -> [a]
++ t -> [Int] -> [t]
finish (t
jt -> t -> t
forall a. Num a => a -> a -> a
-t
1) [Int]
ks
  finish t
_  []     = []

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

{-
-- more variations:

_dualPartition_b :: [Int] -> [Int]
_dualPartition_b [] = []
_dualPartition_b xs = go 1 (diffSequence xs) [] where
  go !i (d:ds) acc = go (i+1) ds ((d,i):acc)
  go _  []     acc = concatMap (\(d,i) -> replicate d i) acc

_dualPartition_c :: [Int] -> [Int]
_dualPartition_c [] = []
_dualPartition_c xs = reverse $ concat $ zipWith f [1..] (diffSequence xs) where
  f _ 0 = []
  f k d = replicate d k
-}

-- | A simpler, but bit slower (about twice?) implementation of dual partition
_dualPartitionNaive :: [Int] -> [Int]
_dualPartitionNaive :: [Int] -> [Int]
_dualPartitionNaive [] = []
_dualPartitionNaive xs :: [Int]
xs@(Int
k:[Int]
_) = [ [Int] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length ([Int] -> Int) -> [Int] -> Int
forall a b. (a -> b) -> a -> b
$ (Int -> Bool) -> [Int] -> [Int]
forall a. (a -> Bool) -> [a] -> [a]
filter (Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>=Int
i) [Int]
xs | Int
i <- [Int
1..Int
k] ]

-- | From a sequence @[a1,a2,..,an]@ computes the sequence of differences
-- @[a1-a2,a2-a3,...,an-0]@
_diffSequence :: [Int] -> [Int]
_diffSequence :: [Int] -> [Int]
_diffSequence = [Int] -> [Int]
forall a. Num a => [a] -> [a]
go where
  go :: [a] -> [a]
go (a
x:ys :: [a]
ys@(a
y:[a]
_)) = (a
xa -> a -> a
forall a. Num a => a -> a -> a
-a
y) a -> [a] -> [a]
forall a. a -> [a] -> [a]
: [a] -> [a]
go [a]
ys 
  go [a
x] = [a
x]
  go []  = []

-- | Example:
--
-- > _elements [5,4,1] ==
-- >   [ (1,1), (1,2), (1,3), (1,4), (1,5)
-- >   , (2,1), (2,2), (2,3), (2,4)
-- >   , (3,1)
-- >   ]
--

_elements :: [Int] -> [(Int,Int)]
_elements :: [Int] -> [(Int, Int)]
_elements [Int]
shape = [ (Int
i,Int
j) | (Int
i,Int
l) <- [Int] -> [Int] -> [(Int, Int)]
forall a b. [a] -> [b] -> [(a, b)]
zip [Int
1..] [Int]
shape, Int
j<-[Int
1..Int
l] ] 

---------------------------------------------------------------------------------
-- * Exponential form

-- | We convert a partition to exponential form.
-- @(i,e)@ mean @(i^e)@; for example @[(1,4),(2,3)]@ corresponds to @(1^4)(2^3) = [2,2,2,1,1,1,1]@. Another example:
--
-- > toExponentialForm (Partition [5,5,3,2,2,2,2,1,1]) == [(1,2),(2,4),(3,1),(5,2)]
--
_toExponentialForm :: [Int] -> [(Int,Int)]
_toExponentialForm :: [Int] -> [(Int, Int)]
_toExponentialForm = [(Int, Int)] -> [(Int, Int)]
forall a. [a] -> [a]
reverse ([(Int, Int)] -> [(Int, Int)])
-> ([Int] -> [(Int, Int)]) -> [Int] -> [(Int, Int)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ([Int] -> (Int, Int)) -> [[Int]] -> [(Int, Int)]
forall a b. (a -> b) -> [a] -> [b]
map (\[Int]
xs -> ([Int] -> Int
forall a. [a] -> a
head [Int]
xs,[Int] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length [Int]
xs)) ([[Int]] -> [(Int, Int)])
-> ([Int] -> [[Int]]) -> [Int] -> [(Int, Int)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [Int] -> [[Int]]
forall a. Eq a => [a] -> [[a]]
group

_fromExponentialForm :: [(Int,Int)] -> [Int]
_fromExponentialForm :: [(Int, Int)] -> [Int]
_fromExponentialForm = (Int -> Int -> Ordering) -> [Int] -> [Int]
forall a. (a -> a -> Ordering) -> [a] -> [a]
sortBy Int -> Int -> Ordering
forall a. Ord a => a -> a -> Ordering
reverseCompare ([Int] -> [Int])
-> ([(Int, Int)] -> [Int]) -> [(Int, Int)] -> [Int]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [(Int, Int)] -> [Int]
forall a. [(a, Int)] -> [a]
go where
  go :: [(a, Int)] -> [a]
go ((a
j,Int
e):[(a, Int)]
rest) = Int -> a -> [a]
forall a. Int -> a -> [a]
replicate Int
e a
j [a] -> [a] -> [a]
forall a. [a] -> [a] -> [a]
++ [(a, Int)] -> [a]
go [(a, Int)]
rest
  go []           = []   

---------------------------------------------------------------------------------
-- * Generating partitions

-- | Partitions of @d@, as lists
_partitions :: Int -> [[Int]]
_partitions :: Int -> [[Int]]
_partitions Int
d = Int -> Int -> [[Int]]
forall a. (Num a, Ord a, Enum a) => a -> a -> [[a]]
go Int
d Int
d where
  go :: a -> a -> [[a]]
go a
_  a
0  = [[]]
  go !a
h !a
n = [ a
aa -> [a] -> [a]
forall a. a -> [a] -> [a]
:[a]
as | a
a<-[a
1..a -> a -> a
forall a. Ord a => a -> a -> a
min a
n a
h], [a]
as <- a -> a -> [[a]]
go a
a (a
na -> a -> a
forall a. Num a => a -> a -> a
-a
a) ]

-- | All integer partitions up to a given degree (that is, all integer partitions whose sum is less or equal to @d@)
_allPartitions :: Int -> [[Int]]
_allPartitions :: Int -> [[Int]]
_allPartitions Int
d = [[[Int]]] -> [[Int]]
forall (t :: * -> *) a. Foldable t => t [a] -> [a]
concat [ Int -> [[Int]]
_partitions Int
i | Int
i <- [Int
0..Int
d] ]

-- | All integer partitions up to a given degree (that is, all integer partitions whose sum is less or equal to @d@),
-- grouped by weight
_allPartitionsGrouped :: Int -> [[[Int]]]
_allPartitionsGrouped :: Int -> [[[Int]]]
_allPartitionsGrouped Int
d = [ Int -> [[Int]]
_partitions Int
i | Int
i <- [Int
0..Int
d] ]

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

-- | Integer partitions of @d@, fitting into a given rectangle, as lists.
_partitions' 
  :: (Int,Int)     -- ^ (height,width)
  -> Int           -- ^ d
  -> [[Int]]        
_partitions' :: (Int, Int) -> Int -> [[Int]]
_partitions' (Int, Int)
_ Int
0 = [[]] 
_partitions' ( Int
0 , Int
_) Int
d = if Int
dInt -> Int -> Bool
forall a. Eq a => a -> a -> Bool
==Int
0 then [[]] else []
_partitions' ( Int
_ , Int
0) Int
d = if Int
dInt -> Int -> Bool
forall a. Eq a => a -> a -> Bool
==Int
0 then [[]] else []
_partitions' (!Int
h ,!Int
w) Int
d = 
  [ Int
iInt -> [Int] -> [Int]
forall a. a -> [a] -> [a]
:[Int]
xs | Int
i <- [Int
1..Int -> Int -> Int
forall a. Ord a => a -> a -> a
min Int
d Int
h] , [Int]
xs <- (Int, Int) -> Int -> [[Int]]
_partitions' (Int
i,Int
wInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1) (Int
dInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
i) ]

---------------------------------------------------------------------------------
-- * Random partitions

-- | Uniformly random partition of the given weight. 
--
-- NOTE: This algorithm is effective for small @n@-s (say @n@ up to a few hundred \/ one thousand it should work nicely),
-- and the first time it is executed may be slower (as it needs to build the table 'partitionCountList' first)
--
-- Algorithm of Nijenhuis and Wilf (1975); see
--
-- * Knuth Vol 4A, pre-fascicle 3B, exercise 47;
--
-- * Nijenhuis and Wilf: Combinatorial Algorithms for Computers and Calculators, chapter 10
--
_randomPartition :: RandomGen g => Int -> g -> ([Int], g)
_randomPartition :: Int -> g -> ([Int], g)
_randomPartition Int
n g
g = ([Int]
p, g
g') where
  ([[Int]
p], g
g') = Int -> Int -> g -> ([[Int]], g)
forall g. RandomGen g => Int -> Int -> g -> ([[Int]], g)
_randomPartitions Int
1 Int
n g
g

-- | Generates several uniformly random partitions of @n@ at the same time.
-- Should be a little bit faster then generating them individually.
--
_randomPartitions 
  :: forall g. RandomGen g 
  => Int   -- ^ number of partitions to generate
  -> Int   -- ^ the weight of the partitions
  -> g -> ([[Int]], g)
_randomPartitions :: Int -> Int -> g -> ([[Int]], g)
_randomPartitions Int
howmany Int
n = Rand g [[Int]] -> g -> ([[Int]], g)
forall g a. Rand g a -> g -> (a, g)
runRand (Rand g [[Int]] -> g -> ([[Int]], g))
-> Rand g [[Int]] -> g -> ([[Int]], g)
forall a b. (a -> b) -> a -> b
$ Int -> RandT g Identity [Int] -> Rand g [[Int]]
forall (m :: * -> *) a. Applicative m => Int -> m a -> m [a]
replicateM Int
howmany (Int -> [(Int, Int)] -> RandT g Identity [Int]
worker Int
n []) where

  cnt :: Int -> Integer
cnt = Int -> Integer
countPartitions
 
  finish :: [(Int,Int)] -> [Int]
  finish :: [(Int, Int)] -> [Int]
finish = [Int] -> [Int]
_mkPartition ([Int] -> [Int])
-> ([(Int, Int)] -> [Int]) -> [(Int, Int)] -> [Int]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ((Int, Int) -> [Int]) -> [(Int, Int)] -> [Int]
forall (t :: * -> *) a b. Foldable t => (a -> [b]) -> t a -> [b]
concatMap (Int, Int) -> [Int]
forall a. (Int, a) -> [a]
f where f :: (Int, a) -> [a]
f (Int
j,a
d) = Int -> a -> [a]
forall a. Int -> a -> [a]
replicate Int
j a
d

  fi :: Int -> Integer 
  fi :: Int -> Integer
fi = Int -> Integer
forall a b. (Integral a, Num b) => a -> b
fromIntegral

  find_jd :: Int -> Integer -> (Int,Int)
  find_jd :: Int -> Integer -> (Int, Int)
find_jd Int
m Integer
capm = Integer -> [(Int, Int)] -> (Int, Int)
go Integer
0 [ (Int
j,Int
d) | Int
j<-[Int
1..Int
n], Int
d<-[Int
1..Int -> Int -> Int
forall a. Integral a => a -> a -> a
div Int
m Int
j] ] where
    go :: Integer -> [(Int,Int)] -> (Int,Int)
    go :: Integer -> [(Int, Int)] -> (Int, Int)
go !Integer
s []   = (Int
1,Int
1)       -- ??
    go !Integer
s [(Int, Int)
jd] = (Int, Int)
jd          -- ??
    go !Integer
s (jd :: (Int, Int)
jd@(Int
j,Int
d):[(Int, Int)]
rest) = 
      if Integer
s' Integer -> Integer -> Bool
forall a. Ord a => a -> a -> Bool
> Integer
capm 
        then (Int, Int)
jd 
        else Integer -> [(Int, Int)] -> (Int, Int)
go Integer
s' [(Int, Int)]
rest
      where
        s' :: Integer
s' = Integer
s Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
+ Int -> Integer
fi Int
d Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
* Int -> Integer
cnt (Int
m Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
jInt -> Int -> Int
forall a. Num a => a -> a -> a
*Int
d)

  worker :: Int -> [(Int,Int)] -> Rand g [Int]
  worker :: Int -> [(Int, Int)] -> RandT g Identity [Int]
worker  Int
0 [(Int, Int)]
acc = [Int] -> RandT g Identity [Int]
forall (m :: * -> *) a. Monad m => a -> m a
return ([Int] -> RandT g Identity [Int])
-> [Int] -> RandT g Identity [Int]
forall a b. (a -> b) -> a -> b
$ [(Int, Int)] -> [Int]
finish [(Int, Int)]
acc
  worker !Int
m [(Int, Int)]
acc = do
    Integer
capm <- (Integer, Integer) -> Rand g Integer
forall g a. (RandomGen g, Random a) => (a, a) -> Rand g a
randChoose (Integer
0, (Int -> Integer
fi Int
m) Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
* Int -> Integer
cnt Int
m Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
- Integer
1)
    let jd :: (Int, Int)
jd@(!Int
j,!Int
d) = Int -> Integer -> (Int, Int)
find_jd Int
m Integer
capm
    Int -> [(Int, Int)] -> RandT g Identity [Int]
worker (Int
m Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
jInt -> Int -> Int
forall a. Num a => a -> a -> a
*Int
d) ((Int, Int)
jd(Int, Int) -> [(Int, Int)] -> [(Int, Int)]
forall a. a -> [a] -> [a]
:[(Int, Int)]
acc)


---------------------------------------------------------------------------------
-- * Dominance order 

-- | @q \`dominates\` p@ returns @True@ if @q >= p@ in the dominance order of partitions
-- (this is partial ordering on the set of partitions of @n@).
--
-- See <http://en.wikipedia.org/wiki/Dominance_order>
--
_dominates :: [Int] -> [Int] -> Bool
_dominates :: [Int] -> [Int] -> Bool
_dominates [Int]
qs [Int]
ps
  = [Bool] -> Bool
forall (t :: * -> *). Foldable t => t Bool -> Bool
and ([Bool] -> Bool) -> [Bool] -> Bool
forall a b. (a -> b) -> a -> b
$ (Int -> Int -> Bool) -> [Int] -> [Int] -> [Bool]
forall a b c. (a -> b -> c) -> [a] -> [b] -> [c]
zipWith Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
(>=) ([Int] -> [Int]
sums ([Int]
qs [Int] -> [Int] -> [Int]
forall a. [a] -> [a] -> [a]
++ Int -> [Int]
forall a. a -> [a]
repeat Int
0)) ([Int] -> [Int]
sums [Int]
ps)
  where
    sums :: [Int] -> [Int]
sums = (Int -> Int -> Int) -> Int -> [Int] -> [Int]
forall b a. (b -> a -> b) -> b -> [a] -> [b]
scanl Int -> Int -> Int
forall a. Num a => a -> a -> a
(+) Int
0

-- | Lists all partitions of the same weight as @lambda@ and also dominated by @lambda@
-- (that is, all partial sums are less or equal):
--
-- > dominatedPartitions lam == [ mu | mu <- partitions (weight lam), lam `dominates` mu ]
-- 
_dominatedPartitions :: [Int] -> [[Int]]
_dominatedPartitions :: [Int] -> [[Int]]
_dominatedPartitions []     = [[]]
_dominatedPartitions [Int]
lambda = Int -> Int -> [Int] -> Int -> [[Int]]
forall a. (Num a, Ord a, Enum a) => a -> a -> [a] -> a -> [[a]]
go ([Int] -> Int
forall a. [a] -> a
head [Int]
lambda) Int
w [Int]
dsums Int
0 where

  n :: Int
n = [Int] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length [Int]
lambda
  w :: Int
w = [Int] -> Int
forall (t :: * -> *) a. (Foldable t, Num a) => t a -> a
sum    [Int]
lambda
  dsums :: [Int]
dsums = (Int -> Int -> Int) -> [Int] -> [Int]
forall a. (a -> a -> a) -> [a] -> [a]
scanl1 Int -> Int -> Int
forall a. Num a => a -> a -> a
(+) ([Int]
lambda [Int] -> [Int] -> [Int]
forall a. [a] -> [a] -> [a]
++ Int -> [Int]
forall a. a -> [a]
repeat Int
0)

  go :: a -> a -> [a] -> a -> [[a]]
go a
_   a
0 [a]
_       a
_  = [[]]
  go !a
h !a
w (!a
d:[a]
ds) !a
e  
    | a
w a -> a -> Bool
forall a. Ord a => a -> a -> Bool
>  a
0  = [ (a
aa -> [a] -> [a]
forall a. a -> [a] -> [a]
:[a]
as) | a
a <- [a
1..a -> a -> a
forall a. Ord a => a -> a -> a
min a
h (a
da -> a -> a
forall a. Num a => a -> a -> a
-a
e)] , [a]
as <- a -> a -> [a] -> a -> [[a]]
go a
a (a
wa -> a -> a
forall a. Num a => a -> a -> a
-a
a) [a]
ds (a
ea -> a -> a
forall a. Num a => a -> a -> a
+a
a) ] 
    | a
w a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
0  = [[]]
    | a
w a -> a -> Bool
forall a. Ord a => a -> a -> Bool
<  a
0  = [Char] -> [[a]]
forall a. HasCallStack => [Char] -> a
error [Char]
"_dominatedPartitions: fatal error; shouldn't happen"

-- | Lists all partitions of the sime weight as @mu@ and also dominating @mu@
-- (that is, all partial sums are greater or equal):
--
-- > dominatingPartitions mu == [ lam | lam <- partitions (weight mu), lam `dominates` mu ]
-- 
_dominatingPartitions :: [Int] -> [[Int]]
_dominatingPartitions :: [Int] -> [[Int]]
_dominatingPartitions []     = [[]]
_dominatingPartitions [Int]
mu     = Int -> Int -> [Int] -> Int -> [[Int]]
forall a. (Num a, Ord a, Enum a) => a -> a -> [a] -> a -> [[a]]
go Int
w Int
w [Int]
dsums Int
0 where

  n :: Int
n = [Int] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length [Int]
mu
  w :: Int
w = [Int] -> Int
forall (t :: * -> *) a. (Foldable t, Num a) => t a -> a
sum    [Int]
mu
  dsums :: [Int]
dsums = (Int -> Int -> Int) -> [Int] -> [Int]
forall a. (a -> a -> a) -> [a] -> [a]
scanl1 Int -> Int -> Int
forall a. Num a => a -> a -> a
(+) ([Int]
mu [Int] -> [Int] -> [Int]
forall a. [a] -> [a] -> [a]
++ Int -> [Int]
forall a. a -> [a]
repeat Int
0)

  go :: a -> a -> [a] -> a -> [[a]]
go a
_   a
0 [a]
_       a
_  = [[]]
  go !a
h !a
w (!a
d:[a]
ds) !a
e  
    | a
w a -> a -> Bool
forall a. Ord a => a -> a -> Bool
>  a
0  = [ (a
aa -> [a] -> [a]
forall a. a -> [a] -> [a]
:[a]
as) | a
a <- [a -> a -> a
forall a. Ord a => a -> a -> a
max a
0 (a
da -> a -> a
forall a. Num a => a -> a -> a
-a
e)..a -> a -> a
forall a. Ord a => a -> a -> a
min a
h a
w] , [a]
as <- a -> a -> [a] -> a -> [[a]]
go a
a (a
wa -> a -> a
forall a. Num a => a -> a -> a
-a
a) [a]
ds (a
ea -> a -> a
forall a. Num a => a -> a -> a
+a
a) ] 
    | a
w a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
0  = [[]]
    | a
w a -> a -> Bool
forall a. Ord a => a -> a -> Bool
<  a
0  = [Char] -> [[a]]
forall a. HasCallStack => [Char] -> a
error [Char]
"_dominatingPartitions: fatal error; shouldn't happen"

--------------------------------------------------------------------------------
-- * Partitions with given number of parts

-- | Lists partitions of @n@ into @k@ parts.
--
-- > sort (partitionsWithKParts k n) == sort [ p | p <- partitions n , numberOfParts p == k ]
--
-- Naive recursive algorithm.
--
_partitionsWithKParts 
  :: Int    -- ^ @k@ = number of parts
  -> Int    -- ^ @n@ = the integer we partition
  -> [[Int]]
_partitionsWithKParts :: Int -> Int -> [[Int]]
_partitionsWithKParts Int
k Int
n = Int -> Int -> Int -> [[Int]]
forall a. (Ord a, Num a, Enum a) => a -> a -> a -> [[a]]
go Int
n Int
k Int
n where
{-
  h = max height
  k = number of parts
  n = integer
-}
  go :: a -> a -> a -> [[a]]
go !a
h !a
k !a
n 
    | a
k a -> a -> Bool
forall a. Ord a => a -> a -> Bool
<  a
0     = []
    | a
k a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
0     = if a
ha -> a -> Bool
forall a. Ord a => a -> a -> Bool
>=a
0 Bool -> Bool -> Bool
&& a
na -> a -> Bool
forall a. Eq a => a -> a -> Bool
==a
0 then [[] ] else []
    | a
k a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
1     = if a
ha -> a -> Bool
forall a. Ord a => a -> a -> Bool
>=a
n Bool -> Bool -> Bool
&& a
na -> a -> Bool
forall a. Ord a => a -> a -> Bool
>=a
1 then [[a
n]] else []
    | Bool
otherwise  = [ a
aa -> [a] -> [a]
forall a. a -> [a] -> [a]
:[a]
p | a
a <- [a
1..(a -> a -> a
forall a. Ord a => a -> a -> a
min a
h (a
na -> a -> a
forall a. Num a => a -> a -> a
-a
ka -> a -> a
forall a. Num a => a -> a -> a
+a
1))] , [a]
p <- a -> a -> a -> [[a]]
go a
a (a
ka -> a -> a
forall a. Num a => a -> a -> a
-a
1) (a
na -> a -> a
forall a. Num a => a -> a -> a
-a
a) ]

--------------------------------------------------------------------------------
-- * Partitions with only odd\/distinct parts

-- | Partitions of @n@ with only odd parts
_partitionsWithOddParts :: Int -> [[Int]]
_partitionsWithOddParts :: Int -> [[Int]]
_partitionsWithOddParts Int
d = (Int -> Int -> [[Int]]
forall a. (Num a, Ord a, Enum a) => a -> a -> [[a]]
go Int
d Int
d) where
  go :: a -> a -> [[a]]
go a
_  a
0  = [[]]
  go !a
h !a
n = [ a
aa -> [a] -> [a]
forall a. a -> [a] -> [a]
:[a]
as | a
a<-[a
1,a
3..a -> a -> a
forall a. Ord a => a -> a -> a
min a
n a
h], [a]
as <- a -> a -> [[a]]
go a
a (a
na -> a -> a
forall a. Num a => a -> a -> a
-a
a) ]

{-
-- | Partitions of @n@ with only even parts
--
-- Note: this is not very interesting, it's just @(map.map) (2*) $ _partitions (div n 2)@
--
_partitionsWithEvenParts :: Int -> [[Int]]
_partitionsWithEvenParts d = (go d d) where
  go _  0  = [[]]
  go !h !n = [ a:as | a<-[2,4..min n h], as <- go a (n-a) ]
-}

-- | Partitions of @n@ with distinct parts.
-- 
-- Note:
--
-- > length (partitionsWithDistinctParts d) == length (partitionsWithOddParts d)
--
_partitionsWithDistinctParts :: Int -> [[Int]]
_partitionsWithDistinctParts :: Int -> [[Int]]
_partitionsWithDistinctParts Int
d = (Int -> Int -> [[Int]]
forall a. (Num a, Ord a, Enum a) => a -> a -> [[a]]
go Int
d Int
d) where
  go :: a -> a -> [[a]]
go a
_  a
0  = [[]]
  go !a
h !a
n = [ a
aa -> [a] -> [a]
forall a. a -> [a] -> [a]
:[a]
as | a
a<-[a
1..a -> a -> a
forall a. Ord a => a -> a -> a
min a
n a
h], [a]
as <- a -> a -> [[a]]
go (a
aa -> a -> a
forall a. Num a => a -> a -> a
-a
1) (a
na -> a -> a
forall a. Num a => a -> a -> a
-a
a) ]

--------------------------------------------------------------------------------
-- * Sub- and super-partitions of a given partition

-- | Returns @True@ of the first partition is a subpartition (that is, fit inside) of the second.
-- This includes equality
_isSubPartitionOf :: [Int] -> [Int] -> Bool
_isSubPartitionOf :: [Int] -> [Int] -> Bool
_isSubPartitionOf [Int]
ps [Int]
qs = [Bool] -> Bool
forall (t :: * -> *). Foldable t => t Bool -> Bool
and ([Bool] -> Bool) -> [Bool] -> Bool
forall a b. (a -> b) -> a -> b
$ (Int -> Int -> Bool) -> [Int] -> [Int] -> [Bool]
forall a b c. (a -> b -> c) -> [a] -> [b] -> [c]
zipWith Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
(<=) [Int]
ps ([Int]
qs [Int] -> [Int] -> [Int]
forall a. [a] -> [a] -> [a]
++ Int -> [Int]
forall a. a -> [a]
repeat Int
0)

-- | This is provided for convenience\/completeness only, as:
--
-- > isSuperPartitionOf q p == isSubPartitionOf p q
--
_isSuperPartitionOf :: [Int] -> [Int] -> Bool
_isSuperPartitionOf :: [Int] -> [Int] -> Bool
_isSuperPartitionOf [Int]
qs [Int]
ps = [Bool] -> Bool
forall (t :: * -> *). Foldable t => t Bool -> Bool
and ([Bool] -> Bool) -> [Bool] -> Bool
forall a b. (a -> b) -> a -> b
$ (Int -> Int -> Bool) -> [Int] -> [Int] -> [Bool]
forall a b c. (a -> b -> c) -> [a] -> [b] -> [c]
zipWith Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
(<=) [Int]
ps ([Int]
qs [Int] -> [Int] -> [Int]
forall a. [a] -> [a] -> [a]
++ Int -> [Int]
forall a. a -> [a]
repeat Int
0)


-- | Sub-partitions of a given partition with the given weight:
--
-- > sort (subPartitions d q) == sort [ p | p <- partitions d, isSubPartitionOf p q ]
--
_subPartitions :: Int -> [Int] -> [[Int]]
_subPartitions :: Int -> [Int] -> [[Int]]
_subPartitions Int
d [Int]
big
  | [Int] -> Bool
forall (t :: * -> *) a. Foldable t => t a -> Bool
null [Int]
big       = if Int
dInt -> Int -> Bool
forall a. Eq a => a -> a -> Bool
==Int
0 then [[]] else []
  | Int
d Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> [Int] -> Int
forall a. Num a => [a] -> a
sum' [Int]
big   = []
  | Int
d Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
0          = []
  | Bool
otherwise      = Int -> Int -> [Int] -> [[Int]]
go Int
d ([Int] -> Int
forall a. [a] -> a
head [Int]
big) [Int]
big
  where
    go :: Int -> Int -> [Int] -> [[Int]]
    go :: Int -> Int -> [Int] -> [[Int]]
go !Int
k !Int
h []      = if Int
kInt -> Int -> Bool
forall a. Eq a => a -> a -> Bool
==Int
0 then [[]] else []
    go !Int
k !Int
h (Int
b:[Int]
bs) 
      | Int
kInt -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<Int
0 Bool -> Bool -> Bool
|| Int
hInt -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<Int
0   = []
      | Int
kInt -> Int -> Bool
forall a. Eq a => a -> a -> Bool
==Int
0         = [[]]
      | Int
hInt -> Int -> Bool
forall a. Eq a => a -> a -> Bool
==Int
0         = []
      | Bool
otherwise    = [ Int
thisInt -> [Int] -> [Int]
forall a. a -> [a] -> [a]
:[Int]
rest | Int
this <- [Int
1..Int -> Int -> Int
forall a. Ord a => a -> a -> a
min Int
h Int
b] , [Int]
rest <- Int -> Int -> [Int] -> [[Int]]
go (Int
kInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
this) Int
this [Int]
bs ]

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

-- | All sub-partitions of a given partition
_allSubPartitions :: [Int] -> [[Int]]
_allSubPartitions :: [Int] -> [[Int]]
_allSubPartitions [Int]
big 
  | [Int] -> Bool
forall (t :: * -> *) a. Foldable t => t a -> Bool
null [Int]
big   = [[]]
  | Bool
otherwise  = Int -> [Int] -> [[Int]]
forall a. (Num a, Ord a, Enum a) => a -> [a] -> [[a]]
go ([Int] -> Int
forall a. [a] -> a
head [Int]
big) [Int]
big
  where
    go :: a -> [a] -> [[a]]
go a
_  [] = [[]]
    go !a
h (a
b:[a]
bs) 
      | a
ha -> a -> Bool
forall a. Eq a => a -> a -> Bool
==a
0         = []
      | Bool
otherwise    = [] [a] -> [[a]] -> [[a]]
forall a. a -> [a] -> [a]
: [ a
thisa -> [a] -> [a]
forall a. a -> [a] -> [a]
:[a]
rest | a
this <- [a
1..a -> a -> a
forall a. Ord a => a -> a -> a
min a
h a
b] , [a]
rest <- a -> [a] -> [[a]]
go a
this [a]
bs ]

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

-- | Super-partitions of a given partition with the given weight:
--
-- > sort (superPartitions d p) == sort [ q | q <- partitions d, isSubPartitionOf p q ]
--
_superPartitions :: Int -> [Int] -> [[Int]]
_superPartitions :: Int -> [Int] -> [[Int]]
_superPartitions Int
dd [Int]
small
  | Int
dd Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
w0     = []
  | [Int] -> Bool
forall (t :: * -> *) a. Foldable t => t a -> Bool
null [Int]
small  = Int -> [[Int]]
_partitions Int
dd
  | Bool
otherwise   = Int -> Int -> Int -> [Int] -> [[Int]]
forall a. (Ord a, Num a, Enum a) => a -> a -> a -> [a] -> [[a]]
go Int
dd Int
w1 Int
dd ([Int]
small [Int] -> [Int] -> [Int]
forall a. [a] -> [a] -> [a]
++ Int -> [Int]
forall a. a -> [a]
repeat Int
0)
  where
    w0 :: Int
w0 = [Int] -> Int
forall a. Num a => [a] -> a
sum' [Int]
small
    w1 :: Int
w1 = Int
w0 Int -> Int -> Int
forall a. Num a => a -> a -> a
- [Int] -> Int
forall a. [a] -> a
head [Int]
small
    -- d = remaining weight of the outer partition we are constructing
    -- w = remaining weight of the inner partition (we need to reserve at least this amount)
    -- h = max height (decreasing)
    go :: a -> a -> a -> [a] -> [[a]]
go !a
d !a
w !a
h (!a
a:as :: [a]
as@(a
b:[a]
_)) 
      | a
d a -> a -> Bool
forall a. Ord a => a -> a -> Bool
< a
0     = []
      | a
d a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
0    = if a
a a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
0 then [[]] else []
      | Bool
otherwise = [ a
thisa -> [a] -> [a]
forall a. a -> [a] -> [a]
:[a]
rest | a
this <- [a -> a -> a
forall a. Ord a => a -> a -> a
max a
1 a
a .. a -> a -> a
forall a. Ord a => a -> a -> a
min a
h (a
da -> a -> a
forall a. Num a => a -> a -> a
-a
w)] , [a]
rest <- a -> a -> a -> [a] -> [[a]]
go (a
da -> a -> a
forall a. Num a => a -> a -> a
-a
this) (a
wa -> a -> a
forall a. Num a => a -> a -> a
-a
b) a
this [a]
as ]
    
--------------------------------------------------------------------------------
-- * The Pieri rule

-- | The Pieri rule computes @s[lambda]*h[n]@ as a sum of @s[mu]@-s (each with coefficient 1).
--
-- See for example <http://en.wikipedia.org/wiki/Pieri's_formula>
--
-- | We assume here that @lambda@ is a partition (non-increasing sequence of /positive/ integers)! 
_pieriRule :: [Int] -> Int -> [[Int]] 
_pieriRule :: [Int] -> Int -> [[Int]]
_pieriRule [Int]
lambda Int
n
    | Int
n Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
0     = [[Int]
lambda]
    | Int
n Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<  Int
0     = [] 
    | Bool
otherwise  = Int -> [Int] -> [Int] -> [Int] -> [[Int]]
forall a. (Ord a, Enum a, Num a) => a -> [a] -> [a] -> [a] -> [[a]]
go Int
n [Int]
diffs [Int]
dsums ([Int]
lambda[Int] -> [Int] -> [Int]
forall a. [a] -> [a] -> [a]
++[Int
0]) 
    where
      diffs :: [Int]
diffs = Int
n Int -> [Int] -> [Int]
forall a. a -> [a] -> [a]
: [Int] -> [Int]
_diffSequence [Int]
lambda                 -- maximum we can add to a given row
      dsums :: [Int]
dsums = [Int] -> [Int]
forall a. [a] -> [a]
reverse ([Int] -> [Int]) -> [Int] -> [Int]
forall a b. (a -> b) -> a -> b
$ (Int -> Int -> Int) -> [Int] -> [Int]
forall a. (a -> a -> a) -> [a] -> [a]
scanl1 Int -> Int -> Int
forall a. Num a => a -> a -> a
(+) ([Int] -> [Int]
forall a. [a] -> [a]
reverse [Int]
diffs)    -- partial sums of remaining total we can add
      go :: a -> [a] -> [a] -> [a] -> [[a]]
go !a
k (a
d:[a]
ds) (a
p:ps :: [a]
ps@(a
q:[a]
_)) (a
l:[a]
ls) 
        | a
k a -> a -> Bool
forall a. Ord a => a -> a -> Bool
> a
p     = []
        | Bool
otherwise = [ a
ha -> [a] -> [a]
forall a. a -> [a] -> [a]
:[a]
tl | a
a <- [ a -> a -> a
forall a. Ord a => a -> a -> a
max a
0 (a
ka -> a -> a
forall a. Num a => a -> a -> a
-a
q) .. a -> a -> a
forall a. Ord a => a -> a -> a
min a
d a
k ] , let h :: a
h = a
la -> a -> a
forall a. Num a => a -> a -> a
+a
a , [a]
tl <- a -> [a] -> [a] -> [a] -> [[a]]
go (a
ka -> a -> a
forall a. Num a => a -> a -> a
-a
a) [a]
ds [a]
ps [a]
ls ]
      go !a
k [a
d]    [a]
_      [a
l]    = if a
k a -> a -> Bool
forall a. Ord a => a -> a -> Bool
<= a
d 
                                     then if a
la -> a -> a
forall a. Num a => a -> a -> a
+a
ka -> a -> Bool
forall a. Ord a => a -> a -> Bool
>a
0 then [[a
la -> a -> a
forall a. Num a => a -> a -> a
+a
k]] else [[]]
                                     else []
      go !a
k []     [a]
_      [a]
_      = if a
ka -> a -> Bool
forall a. Eq a => a -> a -> Bool
==a
0 then [[]] else []

-- | The dual Pieri rule computes @s[lambda]*e[n]@ as a sum of @s[mu]@-s (each with coefficient 1)
_dualPieriRule :: [Int] -> Int -> [[Int]] 
_dualPieriRule :: [Int] -> Int -> [[Int]]
_dualPieriRule [Int]
lam Int
n = ([Int] -> [Int]) -> [[Int]] -> [[Int]]
forall a b. (a -> b) -> [a] -> [b]
map [Int] -> [Int]
_dualPartition ([[Int]] -> [[Int]]) -> [[Int]] -> [[Int]]
forall a b. (a -> b) -> a -> b
$ [Int] -> Int -> [[Int]]
_pieriRule ([Int] -> [Int]
_dualPartition [Int]
lam) Int
n

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