Compositions
A weak composition of a non-negative integer $n$ is a sequence $\lambda_1,\dots,\lambda_k$ of non-negative integers $\lambda_i$ such that $n = \lambda_1 + \dots + \lambda_k$. A composition of $n$ is a weak composition consisting of positive integers. The $\lambda_i$ are called the parts of the (weak) composition.
weak_composition — Function
weak_composition(parts::Vector{T}; check::Bool = true) where T <: IntegerUnionReturn the weak composition given by the integer sequence parts as an object of type WeakComposition{T}.
If check is true (default), it is checked whether the given sequence defines a weak composition, that is, whether all elements of parts are non-negative.
Examples
julia> W = weak_composition([6, 0, 2, 3]) # the weak composition 6, 0, 2, 3 of 11
[6, 0, 2, 3]
julia> W = weak_composition(Int8[6, 0, 2, 3]) # save the elements in 8-bit integers
Int8[6, 0, 2, 3]composition — Function
composition(parts::Vector{T}; check::Bool = true) where T <: IntegerUnionReturn the composition given by the integer sequence parts as an object of type Composition{T}.
If check is true (default), it is checked whether the given sequence defines a composition, that is, whether all elements of parts are positive.
Examples
julia> C = composition([6, 1, 2, 3]) # the composition 6, 1, 2, 3 of 12
[6, 1, 2, 3]
julia> C = composition(Int8[6, 1, 2, 3]) # save the elements in 8-bit integers
Int8[6, 1, 2, 3]Generating and counting
Unrestricted compositions
compositions — Method
compositions(n::IntegerUnion)Return an iterator over all compositions of a non-negative integer n.
By a composition of n we mean a sequence of positive integers whose sum is n.
Examples
julia> C = compositions(4)
Iterator over the compositions of 4
julia> collect(C)
8-element Vector{Composition{Int64}}:
[4]
[3, 1]
[2, 2]
[1, 3]
[2, 1, 1]
[1, 2, 1]
[1, 1, 2]
[1, 1, 1, 1]number_of_compositions — Method
number_of_compositions(n::IntegerUnion)Return the number of compositions of the non-negative integer n. For n < 0, return 0.
Note that an integer $n$ has infinitely many weak compositions as one may always append zeros to the end of a given weak composition. Without restrictions on the number of parts, we can hence only generate compositions, but not weak compositions.
Restricted compositions
compositions — Method
compositions(n::IntegerUnion, k::IntegerUnion)Return an iterator over all compositions of a non-negative integer n into k parts, produced in lexicographically descending order.
By a composition of n into k parts we mean a sequence of k positive integers whose sum is n.
Examples
julia> C = compositions(4, 2)
Iterator over the compositions of 4 into 2 parts
julia> collect(C)
3-element Vector{Composition{Int64}}:
[3, 1]
[2, 2]
[1, 3]number_of_compositions — Method
number_of_compositions(n::IntegerUnion, k::IntegerUnion)Return the number of compositions of the non-negative integer n into k >= 0 parts. If n < 0 or k < 0, return 0.
Restricted weak compositions
weak_compositions — Function
weak_compositions(n::IntegerUnion, k::IntegerUnion; inplace::Bool=false)Return an iterator over all weak compositions of a non-negative integer n into k parts, produced in lexicographically descending order. Using a smaller integer type for n (e.g. Int8) may increase performance.
If inplace is true, the elements of the iterator may share their memory. This means that an element returned by the iterator may be overwritten 'in place' in the next iteration step. This may result in significantly fewer memory allocations. However, using the in-place version is only meaningful if just one element of the iterator is needed at any time. For example, calling collect on this iterator will not give useful results.
By a weak composition of n into k parts we mean a sequence of k non-negative integers whose sum is n.
Examples
julia> W = weak_compositions(3, 2)
Iterator over the weak compositions of 3 into 2 parts
julia> length(W)
4
julia> collect(W)
4-element Vector{WeakComposition{Int64}}:
[3, 0]
[2, 1]
[1, 2]
[0, 3]number_of_weak_compositions — Method
number_of_weak_compositions(n::IntegerUnion, k::IntegerUnion)Return the number of weak compositions of the non-negative integer n into k >= 0 parts. If n < 0 or k < 0, return 0.
Ascending compositions
ascending_compositions — Function
ascending_compositions(n::IntegerUnion)Return an iterator over all ascending compositions of a non-negative integer n.
By a ascending composition of n we mean a non-decreasing sequence of positive integers whose sum is n.
The implemented algorithm is "AccelAsc" (Algorithm 4.1) in [KO14].
Examples
julia> C = ascending_compositions(4)
Iterator over the ascending compositions of 4
julia> collect(C)
5-element Vector{Composition{Int64}}:
[1, 1, 1, 1]
[1, 1, 2]
[1, 3]
[2, 2]
[4]The number of ascending compositions of $n$ coincides with the number of partitions of $n$.