module Math.Combinat.Partitions
(
Partition
, toPartition
, toPartitionUnsafe
, mkPartition
, isPartition
, fromPartition
, height
, width
, heightWidth
, weight
, _dualPartition
, dualPartition
, _partitions'
, partitions'
, countPartitions'
, _partitions
, partitions
, countPartitions
, allPartitions'
, allPartitions
, countAllPartitions'
, countAllPartitions
)
where
import Data.List
import Math.Combinat.Helper
newtype Partition = Partition [Int] deriving (Eq,Ord,Show,Read)
mkPartition :: [Int] -> Partition
mkPartition xs = Partition $ sortBy (reverseCompare) $ filter (>0) xs
toPartitionUnsafe :: [Int] -> Partition
toPartitionUnsafe = Partition
toPartition :: [Int] -> Partition
toPartition xs = if isPartition xs
then toPartitionUnsafe xs
else error "toPartition: not a partition"
isPartition :: [Int] -> Bool
isPartition [] = True
isPartition [_] = True
isPartition (x:xs@(y:_)) = (x >= y) && isPartition xs
fromPartition :: Partition -> [Int]
fromPartition (Partition part) = part
height :: Partition -> Int
height (Partition part) = case part of
(p:_) -> p
[] -> 0
width :: Partition -> Int
width (Partition part) = length part
heightWidth :: Partition -> (Int,Int)
heightWidth part = (height part, width part)
weight :: Partition -> Int
weight (Partition part) = sum part
dualPartition :: Partition -> Partition
dualPartition (Partition part) = Partition (_dualPartition part)
_dualPartition :: [Int] -> [Int]
_dualPartition [] = []
_dualPartition xs@(k:_) = [ length $ filter (>=i) xs | i <- [1..k] ]
_partitions'
:: (Int,Int)
-> Int
-> [[Int]]
_partitions' _ 0 = [[]]
_partitions' (0,_) d = if d==0 then [[]] else []
_partitions' (_,0) d = if d==0 then [[]] else []
_partitions' (h,w) d =
[ i:xs | i <- [1..min d h] , xs <- _partitions' (i,w1) (di) ]
partitions'
:: (Int,Int)
-> Int
-> [Partition]
partitions' hw d = map toPartitionUnsafe $ _partitions' hw d
countPartitions' :: (Int,Int) -> Int -> Integer
countPartitions' _ 0 = 1
countPartitions' (0,_) d = if d==0 then 1 else 0
countPartitions' (_,0) d = if d==0 then 1 else 0
countPartitions' (h,w) d = sum
[ countPartitions' (i,w1) (di) | i <- [1..min d h] ]
_partitions :: Int -> [[Int]]
_partitions d = _partitions' (d,d) d
partitions :: Int -> [Partition]
partitions d = partitions' (d,d) d
countPartitions :: Int -> Integer
countPartitions d = countPartitions' (d,d) d
allPartitions'
:: (Int,Int)
-> [[Partition]]
allPartitions' (h,w) = [ partitions' (h,w) i | i <- [0..d] ] where d = h*w
allPartitions :: Int -> [[Partition]]
allPartitions d = [ partitions i | i <- [0..d] ]
countAllPartitions' :: (Int,Int) -> Integer
countAllPartitions' (h,w) =
binomial (h+w) (min h w)
countAllPartitions :: Int -> Integer
countAllPartitions d = sum [ countPartitions i | i <- [0..d] ]