Compositions.hs

-- | Compositions. 
-- This module is equivalent to the module "Combinations", 
-- but it turns out that \"compositions\" is the accepted name. I will
-- remove the "Combinations" module in the future.

module Math.Combinat.Compositions where

import Math.Combinat.Numbers (factorial,binomial)

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

-- | Compositions fitting into a given shape and having a given degree.
--   The order is lexicographic, that is, 
--
-- > sort cs == cs where cs = compositions' shape k
--
compositions'  
  :: [Int]         -- ^ shape
  -> Int           -- ^ sum
  -> [[Int]]
compositions' [] 0 = [[]]
compositions' [] _ = []
compositions' shape@(s:ss) n = 
  [ x:xs | x <- [0..min s n] , xs <- compositions' ss (n-x) ] 

countCompositions' :: [Int] -> Int -> Integer
countCompositions' [] 0 = 1
countCompositions' [] _ = 0
countCompositions' shape@(s:ss) n = sum 
  [ countCompositions' ss (n-x) | x <- [0..min s n] ] 

-- | All compositions fitting into a given shape.
allCompositions' :: [Int] -> [[[Int]]]
allCompositions' shape = map (compositions' shape) [0..d] where d = sum shape

-- | Compositions of a given length.
compositions 
  :: Integral a 
  => a       -- ^ length
  -> a       -- ^ sum
  -> [[Int]]
compositions len' d' = compositions' (replicate len d) d where
  len = fromIntegral len'
  d   = fromIntegral d'

-- | # = \\binom { len+d-1 } { len-1 }
countCompositions :: Integral a => a -> a -> Integer
countCompositions len d = binomial (len+d-1) (len-1)

-- | Positive compositions of a given length.
compositions1  
  :: Integral a 
  => a       -- ^ length
  -> a       -- ^ sum
  -> [[Int]]
compositions1 len' d' 
  | len > d = []
  | otherwise = map plus1 $ compositions len (d-len)
  where
    plus1 = map (+1)
    len = fromIntegral len'
    d   = fromIntegral d'

countCompositions1 :: Integral a => a -> a -> Integer
countCompositions1 len d = countCompositions len (d-len)

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