Math.Combinat.Compositions

Compositions.

See eg. http://en.wikipedia.org/wiki/Composition_%28combinatorics%29

generating all compositions

type Composition = [Int]

A composition of an integer n into k parts is an ordered k-tuple of nonnegative (sometimes positive) integers whose sum is n.

compositions'

Arguments

:: [Int]

shape

-> Int

sum

-> [[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

countCompositions' :: [Int] -> Int -> Integer

allCompositions1 :: Int -> [[Composition]]

All positive compositions of a given number (filtrated by the length). Total number of these is 2^(n-1)

allCompositions' :: [Int] -> [[Composition]]

All compositions fitting into a given shape.

compositions

Arguments

:: Integral a

=> a

length

-> a

sum

-> [[Int]]

Nonnegative compositions of a given length.

countCompositions :: Integral a => a -> a -> Integer

# = \binom { len+d-1 } { len-1 }

compositions1

Arguments

:: Integral a

=> a

length

-> a

sum

-> [[Int]]

Positive compositions of a given length.

countCompositions1 :: Integral a => a -> a -> Integer

random compositions

randomComposition :: RandomGen g => Int -> Int -> g -> ([Int], g)

randomComposition k n returns a uniformly random composition of the number n as an (ordered) sum of k nonnegative numbers

randomComposition1 :: RandomGen g => Int -> Int -> g -> ([Int], g)

randomComposition1 k n returns a uniformly random composition of the number n as an (ordered) sum of k positive numbers