Safe Haskell | None |
---|---|

Language | Haskell2010 |

Compositions.

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

## Synopsis

- type Composition = [Int]
- compositions' :: [Int] -> Int -> [[Int]]
- countCompositions' :: [Int] -> Int -> Integer
- allCompositions1 :: Int -> [[Composition]]
- allCompositions' :: [Int] -> [[Composition]]
- compositions :: Integral a => a -> a -> [[Int]]
- countCompositions :: Integral a => a -> a -> Integer
- compositions1 :: Integral a => a -> a -> [[Int]]
- countCompositions1 :: Integral a => a -> a -> Integer
- randomComposition :: RandomGen g => Int -> Int -> g -> ([Int], g)
- randomComposition1 :: RandomGen g => Int -> Int -> g -> ([Int], g)

# 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 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.

Nonnegative compositions of a given length.

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

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

Positive compositions of a given length.

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