SmallCombinatorics

A combinatorics package for Julia based on SmallCollections.jl.

In the examples we assume that the package is loaded together with SmallCollections:

julia> using SmallCollections, SmallCombinatorics

partitions(n::Integer)

Return an iterator over the partitions of n. A partition of n is a weakly decreasing sequence of positive integers that add up to n. Each partition is of type SmallVector{64,Int8}, but this may change in the future.

See also partitions(::Integer, ::Integer).

Examples

julia> partitions(3) |> collect
3-element Vector{SmallVector{64, Int8}}:
 [3]
 [2, 1]
 [1, 1, 1]

julia> partitions(0) |> collect
1-element Vector{SmallVector{64, Int8}}:
 0-element SmallVector{64, Int8}

partitions(n::Integer, k::Integer)

Return an iterator over the partitions of n into k parts. A partition of n is a weakly decreasing sequence of positive integers that add up to n. Each partition is of type SmallVector{64,Int8}, but this may change in the future.

See also partitions(::Integer).

Examples

julia> partitions(7, 3) |> collect
4-element Vector{SmallVector{64, Int8}}:
 [5, 1, 1]
 [4, 2, 1]
 [3, 3, 1]
 [3, 2, 2]

julia> partitions(7, 0) |> collect
SmallVector{64, Int8}[]

julia> partitions(0, 0) |> collect
1-element Vector{SmallVector{64, Int8}}:
 0-element SmallVector{64, Int8}

compositions(n::Integer, k::Integer)

Return an iterator over the compositions of n of length k. A composition of n of length k is a k-tuple of positive integers that add up to n. Each composition is of type SmallVector{16,Int8}, but this may change in the future.

See also weakcompositions, compositions_cumsum.

Examples

julia> compositions(3, 2) |> collect
2-element Vector{SmallVector{16, Int8}}:
 [1, 2]
 [2, 1]

julia> compositions(3, 0) |> collect
SmallVector{16, Int8}[]

julia> compositions(0, 0)  |> collect
1-element Vector{SmallVector{16, Int8}}:
 0-element SmallVector{16, Int8}

compositions_cumsum(n::Integer, k::Integer)

Return an iterator over the cumulative sums of the compositions of n of length k. A composition of n of length k is a k-tuple of positive integers that add up to n. The cumulative sum of such a composition is a vector with k+1 elements, starting with 0 and ending with n. Each vector is of type SmallVector{16,Int8}, but this may change in the future.

See also compositions, weakcompositions_cumsum.

Examples

julia> compositions_cumsum(3, 2) |> collect
2-element Vector{SmallVector{16, Int8}}:
 [0, 1, 3]
 [0, 2, 3]

julia> compositions_cumsum(3, 0) |> collect
SmallVector{16, Int8}[]

julia> compositions_cumsum(0, 0) |> collect
1-element Vector{SmallVector{16, Int8}}:
 [0]

weakcompositions(n::Integer, k::Integer)

Return an iterator over the weak compositions of n of length k. A weak composition of n of length k is a k-tuple of non-negative integers that add up to n. Each composition is of type SmallVector{16,Int8}, but this may change in the future.

See also compositions, weakcompositions_cumsum.

Examples

julia> weakcompositions(3, 2) |> collect
4-element Vector{SmallVector{16, Int8}}:
 [0, 3]
 [1, 2]
 [2, 1]
 [3, 0]

julia> weakcompositions(3, 0) |> collect
SmallVector{16, Int8}[]

julia> weakcompositions(0, 0) |> collect
1-element Vector{SmallVector{16, Int8}}:
 0-element SmallVector{16, Int8}

weakcompositions_cumsum(n::Integer, k::Integer)

Return an iterator over the cumulative sums of the weak compositions of n of length k. A weak composition of n of length k is a k-tuple of non-negative integers that add up to n. The cumulative sum of such a composition is a vector with k+1 elements, starting with 0 and ending with n. Each vector is of type SmallVector{16,Int8}, but this may change in the future.

See also weakcompositions, compositions_cumsum.

Examples

julia> weakcompositions_cumsum(3, 2) |> collect
4-element Vector{SmallVector{16, Int8}}:
 [0, 0, 3]
 [0, 1, 3]
 [0, 2, 3]
 [0, 3, 3]

julia> weakcompositions_cumsum(3, 0) |> collect
SmallVector{16, Int8}[]

julia> weakcompositions_cumsum(0, 0) |> collect
1-element Vector{SmallVector{16, Int8}}:
 [0]

subsets(s::S) where S <: SmallBitSet -> AbstractVector{S}
subsets(n::Integer) -> AbstractVector{SmallBitSet{UInt}}

In the first form, return a vector of length 2^length(s) whose elements are the subsets of the set s.

In the second form the set s is taken to be SmallBitSet(1:n).

See also subsets(::Integer, ::Integer).

Examples

julia> subsets(SmallBitSet{UInt8}([3, 5])) |> collect
4-element Vector{SmallBitSet{UInt8}}:
 SmallBitSet([])
 SmallBitSet([3])
 SmallBitSet([5])
 SmallBitSet([3, 5])

julia> subsets(2) |> collect
4-element Vector{SmallBitSet{UInt64}}:
 SmallBitSet([])
 SmallBitSet([1])
 SmallBitSet([2])
 SmallBitSet([1, 2])

julia> subsets(2)[2]
SmallBitSet{UInt64} with 1 element:
  1

subsets(s::Union{SmallBitSet, AbstractSmallSet}, k::Integer)
subsets(n::Integer, k::Integer)

In the first form, return an iterator that yields all k-element subsets of the set s. The element type of the iterator is a SmallBitSet or SmallSet. If k is negative or larger than length(s), then the iterator is empty.

In the second form the set s is taken to be SmallBitSet(1:n).

See also subsets(::Integer), combinations, setcompositions_parity.

Example

julia> subsets(SmallBitSet{UInt8}(2:2:8), 3) |> collect
4-element Vector{SmallBitSet{UInt8}}:
 SmallBitSet([2, 4, 6])
 SmallBitSet([2, 4, 8])
 SmallBitSet([2, 6, 8])
 SmallBitSet([4, 6, 8])

julia> subsets(3, 2) |> collect
3-element Vector{SmallBitSet{UInt64}}:
 SmallBitSet([1, 2])
 SmallBitSet([1, 3])
 SmallBitSet([2, 3])

julia> subsets(MutableSmallSet{4}('a':'c'), 2) |> collect
3-element Vector{SmallSet{4, Char}}:
 SmallSet{4}(['a', 'b'])
 SmallSet{4}(['a', 'c'])
 SmallSet{4}(['b', 'c'])

julia> subsets(3, 4) |> collect
SmallBitSet{UInt64}[]

setcompositions(s::S, ks::Vararg{Integer,N}) where {S <: SmallBitSet, N}
setcompositions(ks::Vararg{Integer,N}) where N

In the first form, return an iterator that yields all ks-compositions of the set s, that is, all ordered partitions of s into N sets of size ks[1] to ks[N], respectively. The element type is NTuple{N, S}. The partition sizes in ks must be non-negative and add up to length(s).

In the second form the set s is taken to be SmallBitSet(1:sum(ks)). This gives an iterator over all set compositions of the integer sum(ks).

See also subsets, setcompositions_parity.

Examples

julia> setcompositions(SmallBitSet([2, 4, 5]), 1, 2) |> collect
3-element Vector{Tuple{SmallBitSet{UInt64}, SmallBitSet{UInt64}}}:
 (SmallBitSet([2]), SmallBitSet([4, 5]))
 (SmallBitSet([4]), SmallBitSet([2, 5]))
 (SmallBitSet([5]), SmallBitSet([2, 4]))

julia> setcompositions(1, 1, 1) |> collect
6-element Vector{Tuple{SmallBitSet{UInt64}, SmallBitSet{UInt64}, SmallBitSet{UInt64}}}:
 (SmallBitSet([1]), SmallBitSet([2]), SmallBitSet([3]))
 (SmallBitSet([2]), SmallBitSet([1]), SmallBitSet([3]))
 (SmallBitSet([1]), SmallBitSet([3]), SmallBitSet([2]))
 (SmallBitSet([3]), SmallBitSet([1]), SmallBitSet([2]))
 (SmallBitSet([2]), SmallBitSet([3]), SmallBitSet([1]))
 (SmallBitSet([3]), SmallBitSet([2]), SmallBitSet([1]))

julia> setcompositions(SmallBitSet([2, 4, 5]), 1, 0, 2) |> collect
3-element Vector{Tuple{SmallBitSet{UInt64}, SmallBitSet{UInt64}, SmallBitSet{UInt64}}}:
 (SmallBitSet([2]), SmallBitSet([]), SmallBitSet([4, 5]))
 (SmallBitSet([4]), SmallBitSet([]), SmallBitSet([2, 5]))
 (SmallBitSet([5]), SmallBitSet([]), SmallBitSet([2, 4]))

julia> setcompositions(SmallBitSet()) |> collect
1-element Vector{Tuple{}}:
 ()

setcompositions_parity(s::S, ks::Vararg{Integer,N}) where {S <: SmallBitSet, N}
setcompositions_parity(ks::Vararg{Integer,N}) where N

In the first form, return an iterator that yields all ks-compositions of the set s together with the parity of the permutation that puts the elements back into an increasing order. See setcompositions and setcomposition_parity for details. The iterator returns tuples (t, p), where t is of type NTuple{N, S} and the parity p is of type Bool where false means even and true means odd. The partition sizes in ks must be non-negative and add up to length(s).

In the second form the set s is taken to be SmallBitSet(1:sum(ks)).

See also setcompositions, setcomposition_parity.

Examples

julia> setcompositions_parity(SmallBitSet([2, 4, 5]), 1, 2) |> collect
3-element Vector{Tuple{Tuple{SmallBitSet{UInt64}, SmallBitSet{UInt64}}, Bool}}:
 ((SmallBitSet([2]), SmallBitSet([4, 5])), 0)
 ((SmallBitSet([4]), SmallBitSet([2, 5])), 1)
 ((SmallBitSet([5]), SmallBitSet([2, 4])), 0)

julia> all(s == setcomposition_parity(a, b) for ((a, b), s) in setcompositions_parity(1, 2))
true

setcomposition_parity(ss::SmallBitSet...) -> Bool

Return true if an odd number of transpositions is needed to transform the elements of the sets ss into an increasing sequence, and false otherwise. The sets are considered as increasing sequences and assumed to be disjoint.

See also setcompositions_parity.

Examples

julia> s, t, u = SmallBitSet([2, 3, 8]), SmallBitSet([1, 4, 6]), SmallBitSet([5, 7]);

julia> setcomposition_parity(s, t), setcomposition_parity(s, t, u)
(true, false)

combinations(n::Integer, k::Integer)
combinations(s::Union{SmallBitSet, AbstractSmallSet}, k::Integer)
combinations(s::Union{AbstractFixedVector, AbstractSmallVector}, k::Integer)
combinations(s::PackedVector, k::Integer)

Return an iterator that yields all combinations of k elements from the given collection, whose elements are assumed to be distinct. If the first argument is an integer n, then the collection is taken to be SmallBitSet(1:n). If k is negative or exceeds the length of the collection, then the iterator is empty.

With an integer or a set as first argument, combinations is the same as subsets. If the collection is an AbstractFixedVector{N,T} or AbstractSmallVector{N,T}, then the element type of the iterator is SmallVector{N,T}. If the collection is a PackedVector, then the elements of the iterator are of the same type.

The version with an integer or a SmallBitSet as first argument is the fastest.

See also subsets.

Example

julia> combinations(MutableFixedVector{4}('a':'d'), 2) |> collect
6-element Vector{SmallVector{4, Char}}:
 ['a', 'b']
 ['a', 'c']
 ['b', 'c']
 ['a', 'd']
 ['b', 'd']
 ['c', 'd']

permutations(n::Integer)

Return an iterator that yields all permutations of the integers from 1 to n. The argument n must be between 0 and 16.

This is a short form for permutations(v) with v = SmallVector{16,Int8}(1:n)). (Capacity and element type of v may change in the future.)

See also permutations(::SmallVector), permutations_parity_transposition.

Examples

julia> permutations(3) |> collect
6-element Vector{SmallVector{16, Int8}}:
 [1, 2, 3]
 [2, 1, 3]
 [3, 1, 2]
 [1, 3, 2]
 [2, 3, 1]
 [3, 2, 1]

julia> permutations(0) |> collect
1-element Vector{SmallVector{16, Int8}}:
 0-element SmallVector{16, Int8}

permutations(v::Union{AbstractSmallVector, AbstractFixedVector, PackedVector})

Return an iterator that yields all permutations of the vector v, whose elements are assumed to be distinct.

At present, the elements of the iterator are of type SmallVector{N,T} where N is the capacity of v and T the element type. The identity permutation is returned first.

See also permutations(::Integer), permutations_parity_transposition, multiset_permutations.

Example

julia> permutations(FixedVector{3}('a':'c')) |> collect
6-element Vector{SmallVector{3, Char}}:
 ['a', 'b', 'c']
 ['b', 'a', 'c']
 ['c', 'a', 'b']
 ['a', 'c', 'b']
 ['b', 'c', 'a']
 ['c', 'b', 'a']

julia> permutations(SmallVector{4,Symbol}()) |> collect
1-element Vector{SmallVector{4, Symbol}}:
 0-element SmallVector{4, Symbol}

permutations_parity_transposition(n::Integer)

This is a short form for permutations_parity_transposition(v) with v = SmallVector{16,Int8}(1:n)). (Capacity and element type of v may change in the future.) The argument n must be between 0 and 16.

See also permutations, permutations_parity_transposition(n::SmallVector).

Examples

julia> permutations_parity_transposition(3) |> collect
6-element Vector{Tuple{SmallVector{16, Int8}, Bool, Tuple{Int64, Int64}}}:
 ([1, 2, 3], 0, (0, 0))
 ([2, 1, 3], 1, (1, 2))
 ([3, 1, 2], 0, (1, 3))
 ([1, 3, 2], 1, (1, 2))
 ([2, 3, 1], 0, (1, 3))
 ([3, 2, 1], 1, (1, 2))

julia> permutations_parity_transposition(0) |> collect
1-element Vector{Tuple{SmallVector{16, Int8}, Bool, Tuple{Int64, Int64}}}:
 ([], 0, (0, 0))

permutations_parity_transposition(v::Union{AbstractSmallVector, AbstractFixedVector, PackedVector)

Return an iterator that yields all permutations p of the elements of v together with some extra data. The first element of the tuple returned is the permutation p. The second element is the parity of p (false for even and true for odd permutations). The third element is a pair (i, j) that indicates the transposition t by which p differs from the previously returned permutation q. (More precisely, the new permutations p is obtained by first applying t and then q.)

The iterator returns the identity permutation first; in this case the transposition pair is set to (0, 0). The true transpositions (i, j) satisfy i < j. At present, each permutation is of type SmallVector{N,T} where N is the capacity of v and T the element type.

See also permutations, permutations_parity_transposition(n::Integer).

Examples

julia> v = SmallVector{4}('a':'c');

julia> permutations_parity_transposition(v) |> collect
6-element Vector{Tuple{SmallVector{4, Char}, Bool, Tuple{Int64, Int64}}}:
 (['a', 'b', 'c'], 0, (0, 0))
 (['b', 'a', 'c'], 1, (1, 2))
 (['c', 'a', 'b'], 0, (1, 3))
 (['a', 'c', 'b'], 1, (1, 2))
 (['b', 'c', 'a'], 0, (1, 3))
 (['c', 'b', 'a'], 1, (1, 2))

julia> v = SmallVector{4,String}();

julia> permutations_parity_transposition(v) |> collect
1-element Vector{Tuple{SmallVector{4, String}, Bool, Tuple{Int64, Int64}}}:
 ([], 0, (0, 0))

multiset_permutations(v::Union{AbstractSmallVector, AbstractFixedVector, PackedVector}; [sorted = false])

Return an iterator over all multiset permutations of v, that is, all permutations where equal elements are not distinguished. The element type T must have an ordering. If sorted is true, then v is assumed to be sorted.

At present, the element type must satisfy isbitstype(T), and the iterator yields elements of type SmallVector{N,T} where N is the capacity of v.

See also permutations, Base.isbitstype.

Example

julia> v = SmallVector{8,Int8}([1, 2, 1]);

julia> multiset_permutations(v) |> collect
3-element Vector{SmallVector{8, Int8}}:
 [1, 1, 2]
 [1, 2, 1]
 [2, 1, 1]