Compositions.hs

-- | Compositions. 
--
-- See eg. <http://en.wikipedia.org/wiki/Composition_%28combinatorics%29>
--

module Math.Combinat.Compositions where

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

import System.Random

import Math.Combinat.Sets    ( randomChoice )
import Math.Combinat.Numbers ( factorial , binomial )
import Math.Combinat.Helper

--------------------------------------------------------------------------------
-- * generating all compositions

-- | A /composition/ of an integer @n@ into @k@ parts is an ordered @k@-tuple of nonnegative (sometimes positive) integers
-- whose sum is @n@.
type Composition = [Int]

-- | 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 positive compositions of a given number (filtrated by the length). 
-- Total number of these is @2^(n-1)@
allCompositions1 :: Int -> [[Composition]]
allCompositions1 n = map (\d -> compositions1 d n) [1..n] 

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

-- | Nonnegative 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)

--------------------------------------------------------------------------------
-- * random compositions

-- | @randomComposition k n@ returns a uniformly random composition 
-- of the number @n@ as an (ordered) sum of @k@ /nonnegative/ numbers
randomComposition :: RandomGen g => Int -> Int -> g -> ([Int],g)
randomComposition k n g0 = 
  if k<1 || n<0 
    then error "randomComposition: k should be positive, and n should be nonnegative" 
    else (comp, g1) 
  where
    (cs,g1) = randomChoice (k-1) (n+k-1) g0
    comp = pairsWith (\x y -> y-x-1) (0 : cs ++ [n+k])
  
-- | @randomComposition1 k n@ returns a uniformly random composition 
-- of the number @n@ as an (ordered) sum of @k@ /positive/ numbers
randomComposition1 :: RandomGen g => Int -> Int -> g -> ([Int],g)
randomComposition1 k n g0 = 
  if k<1 || n<k 
    then error "randomComposition1: we require 0 < k <= n" 
    else (comp, g1) 
  where
    (cs,g1) = randomComposition k (n-k) g0 
    comp = map (+1) cs

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