CreatingRhythms-0.0.27.0
Copyright(c) Eric Bailey 2024-2025
LicenseMIT
Maintainereric@ericb.me
Stabilityexperimental
PortabilityPOSIX
Safe HaskellSafe-Inferred
LanguageGHC2021

Data.Rhythm.Compositions

Description

Combinatorial compositions, i.e., partitions in which order is significant.

Synopsis

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