combinat-0.2.6.2: Generation of various combinatorial objects.

Safe HaskellNone
LanguageHaskell98

Math.Combinat.Compositions

Contents

Description

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.

compositions' Source

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.

compositions Source

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 }

compositions1 Source

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