combinat-0.2.7.2: Generate and manipulate various combinatorial objects.

Safe Haskell None Haskell2010

Math.Combinat.Compositions

Description

Compositions.

Synopsis

# generating all compositions

type Composition = [Int] Source

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

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`

allCompositions1 :: Int -> [[Composition]] Source

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

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

All compositions fitting into a given shape.

Arguments

 :: Integral a => a length -> a sum -> [[Int]]

Nonnegative compositions of a given length.

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

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

Arguments

 :: Integral a => a length -> a sum -> [[Int]]

Positive compositions of a given length.

# random compositions

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

`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) Source

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