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.

A combination can be encoded as an array with elements $\lambda_i$. In OSCAR, the parametric type Combination{T} is provided which is a subtype of AbstractVector{T}. Here, T can be any subtype of IntegerUnion. The parametric type allows one to increase performance by using smaller integer types.

julia> @time collect(combinations(20,10));
  0.010399 seconds (184.76 k allocations: 26.782 MiB)

julia> @time collect(combinations(Int8(20),10));
  0.008780 seconds (184.76 k allocations: 12.686 MiB)

Generating

combinations — Method

combinations(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]

source

combinations — Method

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

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