combinat-0.2.10.0: Generate and manipulate various combinatorial objects.

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

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