Combinations

A combination from a set $S$ is a selection $\lambda_1, \lambda_2 \dots \lambda_r$ of elements of $S$ taken without repetition; the order of the elements is considered not to matter. A $k$-combination is a combination consisting of $k$ elements. A general reference on combinations is [Knu11], Section 7.2.1.3.

We represent combinations as objects of type Combination{T}, which is a subtype of AbstractVector{T}, and thus a vector-like object. We use a bespoke type Combination{T} instead of for example a Vector{T} to ensure the semantics of such objects are clear.

For the most basic usage of selecting $k$ values from the set $S = \{1,\ldots,n\}$, the entries of a combination are the values $\lambda_i$ in ascending order:

julia> collect(combinations(4,2))
6-element Vector{Combination{Int64}}:
 [1, 2]
 [1, 3]
 [1, 4]
 [2, 3]
 [2, 4]
 [3, 4]

Here T will be Int by default, but we allow using smaller integer types as this may improve performance or reduce memory consumption.

julia> collect(combinations(Int16(4), Int16(2)))
6-element Vector{Combination{Int16}}:
 Int16[1, 2]
 Int16[1, 3]
 Int16[1, 4]
 Int16[2, 3]
 Int16[2, 4]
 Int16[3, 4]

We also allow using combinations to select k entries from an arbitrary vector v, whose entries have any type T. We do not require that the elements of type T have any kind of ordering, or even that the entries of v are unique. This is equivalent to taking combinations(n,k), where n = length(v), and using the resulting integer combinations as indices for selecting elements of v.

julia> collect(combinations([2,2,1,"a"], 2))
6-element Vector{Combination{Any}}:
 Any[2, 2]
 Any[2, 1]
 Any[2, "a"]
 Any[2, 1]
 Any[2, "a"]
 Any[1, "a"]

Because Combination is a subtype of AbstractVector, many functions that can be used for vectors (1-dimensional arrays) can be used for combinations as well. For example:

julia> C = Combination([6, 4, 4, 2])
[6, 4, 4, 2]

julia> length(C)
4

julia> C[1]
6

Generating and counting

combinations — Function

combinations(n::IntegerUnion, k::IntegerUnion; inplace::Bool=false)

Return an iterator over all $k$-combinations of ${1,...,n}$, produced in lexicographically ascending order.

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.

Examples

julia> C = combinations(4, 3)
Iterator over the 3-combinations of 1:4

julia> collect(C)
4-element Vector{Combination{Int64}}:
 [1, 2, 3]
 [1, 2, 4]
 [1, 3, 4]
 [2, 3, 4]

source

combinations(v::AbstractVector, k::IntegerUnion)

Return an iterator over all k-combinations of a given vector v produced in lexicographically ascending order of the indices.

Examples

julia> C = combinations(['a', 'b', 'c', 'd'], 3)
Iterator over the 3-combinations of ['a', 'b', 'c', 'd']

julia> collect(C)
4-element Vector{Combination{Char}}:
 ['a', 'b', 'c']
 ['a', 'b', 'd']
 ['a', 'c', 'd']
 ['b', 'c', 'd']

source

number_of_combinations — Function

number_of_multicombinations(n::IntegerUnion, k::IntegerUnion)

Return the number of $k$-combinations of ${1, \ldots, n}$. If n < 0 or k < 0, return 0.

source