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
combinations
— Functioncombinations(n::IntegerUnion, k::IntegerUnion)
Return an iterator over all $k$-combinations of ${1,...,n}$, produced in lexicographically ascending order.
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]
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']