SmallCollections.Combinatorics

This module contains functions related to enumerative combinatorics.

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::SmallBitSet, 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 is the type of s. 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), 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(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)

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. The identity permutation is returned first. Each permutation is of type SmallVector{16,Int8}, but this may change in the future.

See also 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_parity_transposition(n::Integer)

Return an iterator that yields all permutations p of the integers from 1 to n 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 argument n must be between 0 and 16. 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. Each permutation is of type SmallVector{16,Int8}, but this may change in the future.

See also permutations.

Examples

julia> permutations_parity_transposition(3) |> collect
6-element Vector{Tuple{SmallVector{16, Int8}, Int64, 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}, Int64, Tuple{Int64, Int64}}}:
 ([], 0, (0, 0))