Copyright | (c) Eric Bailey 2024-2025 |
---|---|
License | MIT |
Maintainer | eric@ericb.me |
Stability | experimental |
Portability | POSIX |
Safe Haskell | Safe-Inferred |
Language | GHC2021 |
Data.Rhythm.Compositions
Description
Combinatorial compositions, i.e., partitions in which order is significant.
Synopsis
- compositions :: Integral a => a -> [Composition]
- compositionsAllowed :: Integral a => [Int] -> a -> [Composition]
- compositionsLength :: Int -> Int -> [[Int]]
- compositionsLengthAllowed :: Int -> [Int] -> Int -> [Composition]
- randomComposition :: Int -> IO Composition
- randomCompositionLength :: Int -> Int -> IO Composition
Documentation
compositions :: Integral a => a -> [Composition] Source #
All positive compositions of a given number.
>>>
compositions 4
[[4],[1,3],[2,2],[3,1],[1,1,2],[1,2,1],[2,1,1],[1,1,1,1]]
compositionsAllowed :: Integral a => [Int] -> a -> [Composition] Source #
All positive compositions with allowed parts.
>>>
compositionsAllowed [1,2] 4
[[2,2],[1,1,2],[1,2,1],[2,1,1],[1,1,1,1]]
compositionsLength :: Int -> Int -> [[Int]] Source #
Positive compositions of a given length.
>>>
compositionsLength 2 5
[[1,4],[2,3],[3,2],[4,1]]
The number of positive compositions of \(n\) into \(k\) parts is given by the following formula.
\[ \begin{align*} C_k(n) &= \binom{n - 1}{k - 1} \\ &= \frac{(n-1)!}{(k-1)!(n-k)!} \end{align*} \]
>>>
let _C k n = toInteger (length (compositionsLength k n))
>>>
let fact n = product [1 .. n]
>>>
_C 2 5 == fact (5 - 1) `div` (fact (2 - 1) * fact (5 - 2))
True
compositionsLengthAllowed :: Int -> [Int] -> Int -> [Composition] Source #
Positive compositions of a given length with allowed parts.
>>>
compositionsLengthAllowed 2 [2,3] 5
[[2,3],[3,2]]
>>>
filter (all (`elem` [2,3])) (compositionsLength 2 5)
[[2,3],[3,2]]
randomComposition :: Int -> IO Composition Source #
Generate a random positive composition of a given number.
>>>
sum <$> randomComposition 13
13
randomCompositionLength :: Int -> Int -> IO Composition Source #
Generate a random positive composition of a given length.
>>>
sum <$> randomCompositionLength 3 33
33