SComb
SComb is Streaming Combinatorics for Elixir. It contains functions such as
permutations/1 and combinations/2. Functions returning large results return
a lazy Stream, so you can take from
results too large to hold in memory, while smaller results may be any
enumerable. The lazy results are a SComb.Sequence, which also knows its size
and can find the element at an index without generating the ones before it.
The package contains only Elixir code without any library dependencies.
Where applicable, the library will return sensible results with repeated parameters: equal elements are interchangeable, so each distinct permutation, combination, subset or partition is returned once. Repeated elements do not need to be next to each other. This is best shown in the examples section.
Installation
Add scomb to the dependencies in your mix.exs:
def deps do
[
{:scomb, "~> 0.3"}
]
endExamples
Permutations
iex> permutations(1..3) |> Enum.to_list
[[1, 2, 3], [2, 1, 3], [1, 3, 2], [3, 1, 2], [2, 3, 1], [3, 2, 1]]
iex> permutations([1, 1, 2]) |> Enum.to_list
[[1, 1, 2], [1, 2, 1], [2, 1, 1]]
iex> permutation_index([1, 3, 2])
2
iex> drop_permutations(1..3, 3) |> Enum.to_list
[[3, 1, 2], [2, 3, 1], [3, 2, 1]]
iex> nth_permutation(1..3, 3)
[3, 1, 2]
iex> count_permutations([1, 1, 2, 2])
6Permuted combinations
iex> permuted_combinations(1..3, 2) |> Enum.to_list
[[1, 2], [2, 1], [1, 3], [3, 1], [2, 3], [3, 2]]
iex> count_permuted_combinations(1..3, 2)
6
iex> nth_permuted_combination(1..3, 2, 3)
[3, 1]Combinations
iex> combinations(1..3, 2) |> Enum.to_list
[[1, 2], [1, 3], [2, 3]]
iex> combinations([1, 1, 2, 2], 3) |> Enum.to_list
[[1, 1, 2], [1, 2, 2]]
iex> nth_combination(1..4, 2, 5)
[3, 4]
iex> count_combinations(1..3, 2)
3Cartesian product
iex> cartesian_product(1..2, 3..4)
[[1, 3], [1, 4], [2, 3], [2, 4]]
iex> cartesian_product([1..2, [:a], 3..4]) |> Enum.to_list
[[1, :a, 3], [1, :a, 4], [2, :a, 3], [2, :a, 4]]
iex> count_cartesian_product([1..2, [:a], 3..4])
4
iex> nth_cartesian_product([1..2, [:a], 3..4], 2)
[2, :a, 3]Subsets
iex> subsets(1..3) |> Enum.to_list
[[], [1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3]]
iex> subsets([1, 1, 2]) |> Enum.to_list
[[], [1], [2], [1, 1], [1, 2], [1, 1, 2]]
iex> count_subsets(1..3)
8
iex> nth_subset(1..3, 4)
[1, 2]Combinations with replacement
iex> combinations_with_replacement(1..3, 2) |> Enum.to_list
[[1, 1], [1, 2], [2, 2], [1, 3], [2, 3], [3, 3]]
iex> count_combinations_with_replacement(1..3, 2)
6
iex> nth_combination_with_replacement(1..3, 2, 4)
[2, 3]Selections
iex> selections(1..2, 3) |> Enum.to_list
[[1, 1, 1], [1, 1, 2], [1, 2, 1], [1, 2, 2], [2, 1, 1], [2, 1, 2],
[2, 2, 1], [2, 2, 2]]
iex> count_selections(1..2, 3)
8
iex> nth_selection(1..2, 3, 5)
[2, 1, 2]Partitions
iex> partitions(1..3) |> Enum.to_list
[[[1, 2, 3]], [[1], [2, 3]], [[2], [1, 3]], [[1, 2], [3]], [[1], [2], [3]]]
iex> partitions([1, 1, 2]) |> Enum.to_list
[[[1, 1, 2]], [[1], [1, 2]], [[1, 1], [2]], [[1], [1], [2]]]
iex> partitions(1..3, min: 2, max: 2) |> Enum.to_list
[[[1], [2, 3]], [[2], [1, 3]], [[1, 2], [3]]]
iex> count_partitions(1..3)
5
iex> nth_partition(1..3, 1)
[[1], [2, 3]]Large results
Results are generated lazily, so you can take from results too large to hold
in memory. The count_*, nth_* and drop_permutations/2 functions, and
permutation_index/1, compute their result directly, without generating the
elements before it. The results of permutations/1, combinations/2,
subsets/1, selections/2, partitions/1, combinations_with_replacement/2,
permuted_combinations/2 and cartesian_product/1 are SComb.Sequence
structs that use these functions, so the Enum functions that look at a position or the size do not
generate the elements before it either.
iex> combinations(1..1000, 500) |> Enum.take(1) |> hd |> Enum.take(3)
[1, 2, 3]
iex> count_permutations(1..30)
265252859812191058636308480000000
iex> nth_permutation(1..30, 10 ** 30) |> permutation_index
1000000000000000000000000000000
iex> Enum.count(permutations(1..30))
265252859812191058636308480000000
iex> Enum.at(permutations(1..30), 10 ** 30) |> Enum.take(3)
[14, 28, 9]
iex> Enum.random(combinations(1..100, 50)) |> length
50Development
Each function in SComb has a naive counterpart in bench/naive.ex, a short
and obviously correct implementation that serves as its specification. The tests
check that both return the same elements, in the same order, for many inputs.
If you find a faster algorithm, and tests are still passing, pull requests will
be considered on Github.
As the package is gradually optimized, we will strive to keep the interface
fixed. Even so, you should not depend on a certain function generating the
exact same sequence between versions of this package. For example, the
permutation/1 function may return the different permutations in different
orders depending on the algorithm used. This will extend to functions like
nth_permutation/2 that could return different values between versions.
The interface of the module is more or less compatible with the clojure math.combinatorics package, which seemed well thought out.
The package is licenced under Apache 2.0, so if you want to copy code from other libraries, please make sure that the license of the source will allow this. Note that the Clojure library mentioned above is licenced more restrictive than this package. Any source contributed is assumed to be free of patents and released under the same license as the rest of the code. Please also refer to the LICENSE file.
Benchmarking
To measure a revised algorithm, we have supplied a mix task to measure the speedup compared to a naive (non streamed) version of the algorithm.
$ mix scomb.benchmark
Each line gives the time taken as a percentage of the naive version, so smaller is faster:
[100% - like naive implementation, smaller is faster]
...
2.05%: combinations - 40-2 elements
5.16%: combinations - 20-10 elements
4.77%: combinations - 10-5 with repeated elements
...
18.85%: partitions - 9 element range
2.84%: partitions - 10 element with repetitions
...
15.16%: permutations - 7 element range
8.22%: permutations - 10 element with repetitions
...Credits
- Martin Svalin / @martinsvalin: Original LazyPermutations module
- Tommy Fisher / @wless1 on Slack: Original combinations and combinations2
- Tallak Tveide / @tallakt: Other stuff
Summary
Functions
Returns all combinations of one element from each of the enumerables in
enums.
This function returns a list containing all combinations of one element
from each a and b
Returns any combination of the elements in enum with exactly k elements,
as a lazy SComb.Sequence. Repeated elements are handled intelligently.
Returns the combinations of k elements of enum in which an element may be
used any number of times, as long as it is in enum. Repeated elements in
enum are one element.
Returns the number of elements cartesian_product/1 would have returned.
Returns the number of elements combinations/2 would have returned.
Returns the number of elements combinations_with_replacement/2 would have
returned.
Returns the number of elements partitions/1 would have returned. For
distinct elements this is the Bell number. With repeated elements the
partitions are counted without generating them, which takes longer the more
distinct values and repeats there are.
Returns the number of elements permutations/1 would have returned.
Returns the number of elements permuted_combinations/2 would have returned.
Returns the number of elements selections/2 would have returned.
Returns the number of elements subsets/1 would have returned.
Calculates permutations starting from element n where n is zero based.
This is more efficient than combining permutations/1 and Stream.drop/2
Returns the nth element that cartesian_product/1 would have returned. n is
zero based, and a negative n counts from the end.
Returns the nth combination that combinations/2 would have returned. n is
zero based, and a negative n counts from the end.
Returns the nth combination that combinations_with_replacement/2 would have
returned. n is zero based, and a negative n counts from the end.
Returns the nth partition that partitions/1 would have returned. n is zero
based, and a negative n counts from the end.
Returns the nth permutation that permutations/1 would have returned. n is
zero based, and a negative n counts from the end.
Returns the nth element that permuted_combinations/2 would have returned.
n is zero based, and a negative n counts from the end.
Returns the nth selection that selections/2 would have returned. n is zero
based, and a negative n counts from the end.
Returns the nth subset that subsets/1 would have returned. n is zero
based, and a negative n counts from the end.
Partitions enum into any groups in sum containing all elements, as a lazy
SComb.Sequence. With the :min or :max option the result is a stream.
Returns the index in the result of what permutations/1 would return, if
permutations/1 was called with enum sorted. The index is zero based.
Returns a lazy SComb.Sequence containing all permutations of the input enum. A
permutation will contain all elements in a different order. Repeated elements
are handled sensibly.
Returns a lazy SComb.Sequence of every permutation of every combination of
k elements of enum: all the ways of picking k elements in a particular
order. Repeated elements are handled sensibly.
Returns all selections of k elements from enum, as a lazy
SComb.Sequence, where each element may be selected any number of times.
Repeated elements in enum are only selected once.
Returns a lazy SComb.Sequence containing all sets possible with any
combination of elements in enum.
Functions
@spec cartesian_product([Enum.t()]) :: SComb.Sequence.t()
Returns all combinations of one element from each of the enumerables in
enums.
Examples
iex> cartesian_product([1..2, [:a], 3..4]) |> Enum.to_list
[[1, :a, 3], [1, :a, 4], [2, :a, 3], [2, :a, 4]]
iex> cartesian_product([]) |> Enum.to_list
[[]]This function returns a list containing all combinations of one element
from each a and b
Example
iex> cartesian_product(1..2, 3..4)
[[1, 3], [1, 4], [2, 3], [2, 4]]@spec combinations(Enum.t(), non_neg_integer()) :: SComb.Sequence.t()
Returns any combination of the elements in enum with exactly k elements,
as a lazy SComb.Sequence. Repeated elements are handled intelligently.
Examples
iex> combinations([1, 2, 3], 2) |> Enum.to_list
[[1, 2], [1, 3], [2, 3]]
iex> combinations([1, 1, 2], 2) |> Enum.to_list
[[1, 1], [1, 2]]@spec combinations_with_replacement(Enum.t(), non_neg_integer()) :: SComb.Sequence.t()
Returns the combinations of k elements of enum in which an element may be
used any number of times, as long as it is in enum. Repeated elements in
enum are one element.
Examples
iex> combinations_with_replacement([1, 2, 3], 2) |> Enum.to_list
[[1, 1], [1, 2], [2, 2], [1, 3], [2, 3], [3, 3]]
iex> combinations_with_replacement([1, 1, 2], 2) |> Enum.to_list
[[1, 1], [1, 2], [2, 2]]@spec count_cartesian_product([Enum.t()]) :: non_neg_integer()
Returns the number of elements cartesian_product/1 would have returned.
Examples
iex> count_cartesian_product([1..2, [:a], 3..5])
6
iex> count_cartesian_product([1..2, []])
0@spec count_combinations(Enum.t(), non_neg_integer()) :: non_neg_integer()
Returns the number of elements combinations/2 would have returned.
Examples
iex> count_combinations([1, 2, 3], 2)
3
iex> count_combinations([1, 1, 2], 2)
2@spec count_combinations_with_replacement(Enum.t(), non_neg_integer()) :: non_neg_integer()
Returns the number of elements combinations_with_replacement/2 would have
returned.
Examples
iex> count_combinations_with_replacement([1, 2, 3], 2)
6@spec count_partitions(Enum.t()) :: pos_integer()
Returns the number of elements partitions/1 would have returned. For
distinct elements this is the Bell number. With repeated elements the
partitions are counted without generating them, which takes longer the more
distinct values and repeats there are.
Examples
iex> count_partitions(1..3)
5
iex> count_partitions([1, 1, 2])
4
iex> count_partitions(1..30)
846749014511809332450147@spec count_permutations(Enum.t()) :: pos_integer()
Returns the number of elements permutations/1 would have returned.
Examples
iex> count_permutations([1, 2, 3])
6
iex> count_permutations([1, 1, 2])
3@spec count_permuted_combinations(Enum.t(), non_neg_integer()) :: non_neg_integer()
Returns the number of elements permuted_combinations/2 would have returned.
Examples
iex> count_permuted_combinations(1..3, 2)
6
iex> count_permuted_combinations([1, 1, 2], 2)
3@spec count_selections(Enum.t(), non_neg_integer()) :: non_neg_integer()
Returns the number of elements selections/2 would have returned.
Examples
iex> count_selections(1..3, 2)
9
iex> count_selections([1, 1, 2], 2)
4@spec count_subsets(Enum.t()) :: pos_integer()
Returns the number of elements subsets/1 would have returned.
Examples
iex> count_subsets([1, 2, 3])
8
iex> count_subsets([1, 1, 2])
6Calculates permutations starting from element n where n is zero based.
This is more efficient than combining permutations/1 and Stream.drop/2
Examples
iex> drop_permutations([1, 2, 3], 2) |> Enum.to_list
[[1, 3, 2], [3, 1, 2], [2, 3, 1], [3, 2, 1]]Returns the nth element that cartesian_product/1 would have returned. n is
zero based, and a negative n counts from the end.
Raises Enum.OutOfBoundsError if there is no such element.
Examples
iex> nth_cartesian_product([1..2, [:a], 3..4], 2)
[2, :a, 3]@spec nth_combination(Enum.t(), non_neg_integer(), integer()) :: list() | no_return()
Returns the nth combination that combinations/2 would have returned. n is
zero based, and a negative n counts from the end.
Raises Enum.OutOfBoundsError if there is no such combination.
Examples
iex> nth_combination([1, 2, 3], 2, 1)
[1, 3]@spec nth_combination_with_replacement(Enum.t(), non_neg_integer(), integer()) :: list() | no_return()
Returns the nth combination that combinations_with_replacement/2 would have
returned. n is zero based, and a negative n counts from the end.
Raises Enum.OutOfBoundsError if there is no such combination.
Examples
iex> nth_combination_with_replacement([1, 2, 3], 2, 4)
[2, 3]Returns the nth partition that partitions/1 would have returned. n is zero
based, and a negative n counts from the end.
Raises Enum.OutOfBoundsError if there is no such partition.
Examples
iex> nth_partition(1..3, 1)
[[1], [2, 3]]
iex> nth_partition([1, 1, 2], -1)
[[1], [1], [2]]Returns the nth permutation that permutations/1 would have returned. n is
zero based, and a negative n counts from the end.
Raises Enum.OutOfBoundsError if there is no such permutation.
Examples
iex> nth_permutation([1, 2, 3], 1)
[2, 1, 3]@spec nth_permuted_combination(Enum.t(), non_neg_integer(), integer()) :: list() | no_return()
Returns the nth element that permuted_combinations/2 would have returned.
n is zero based, and a negative n counts from the end.
Raises Enum.OutOfBoundsError if there is no such element.
Examples
iex> nth_permuted_combination(1..3, 2, 3)
[3, 1]@spec nth_selection(Enum.t(), non_neg_integer(), integer()) :: list() | no_return()
Returns the nth selection that selections/2 would have returned. n is zero
based, and a negative n counts from the end.
Raises Enum.OutOfBoundsError if there is no such selection.
Examples
iex> nth_selection(1..3, 2, 4)
[2, 2]Returns the nth subset that subsets/1 would have returned. n is zero
based, and a negative n counts from the end.
Raises Enum.OutOfBoundsError if there is no such subset.
Examples
iex> nth_subset([1, 2, 3], 4)
[1, 2]@spec partitions(Enum.t(), keyword()) :: SComb.Sequence.t() | Enum.t()
Partitions enum into any groups in sum containing all elements, as a lazy
SComb.Sequence. With the :min or :max option the result is a stream.
Each block holds its elements in the order they appear in enum, and the
blocks are ordered by the last element they hold, so the block with the
last element of enum comes last.
Examples
iex> partitions(1..2) |> Enum.to_list
[[[1, 2]], [[1], [2]]]
iex> partitions([1, 1, 2]) |> Enum.to_list
[[[1, 1, 2]], [[1], [1, 2]], [[1, 1], [2]], [[1], [1], [2]]]
iex> partitions(1..3, min: 2, max: 2) |> Enum.to_list
[[[1], [2, 3]], [[2], [1, 3]], [[1, 2], [3]]]Options
:min- only return partitions with at least this many blocks:max- only return partitions with at most this many blocks
@spec permutation_index(Enum.t()) :: non_neg_integer()
Returns the index in the result of what permutations/1 would return, if
permutations/1 was called with enum sorted. The index is zero based.
Examples
iex> permutation_index([1, 3, 2])
2
iex> nth_permutation([1, 2, 3], 2)
[1, 3, 2]@spec permutations(Enum.t()) :: SComb.Sequence.t()
Returns a lazy SComb.Sequence containing all permutations of the input enum. A
permutation will contain all elements in a different order. Repeated elements
are handled sensibly.
Examples
iex> permutations(1..3) |> Enum.to_list
[[1, 2, 3], [2, 1, 3], [1, 3, 2], [3, 1, 2], [2, 3, 1], [3, 2, 1]]
iex> permutations([1, 1, 2]) |> Enum.to_list
[[1, 1, 2], [1, 2, 1], [2, 1, 1]]@spec permuted_combinations(Enum.t(), non_neg_integer()) :: SComb.Sequence.t()
Returns a lazy SComb.Sequence of every permutation of every combination of
k elements of enum: all the ways of picking k elements in a particular
order. Repeated elements are handled sensibly.
Examples
iex> permuted_combinations(1..3, 2) |> Enum.to_list
[[1, 2], [2, 1], [1, 3], [3, 1], [2, 3], [3, 2]]
iex> permuted_combinations([1, 1, 2], 2) |> Enum.to_list
[[1, 1], [1, 2], [2, 1]]@spec selections(Enum.t(), non_neg_integer()) :: SComb.Sequence.t()
Returns all selections of k elements from enum, as a lazy
SComb.Sequence, where each element may be selected any number of times.
Repeated elements in enum are only selected once.
Examples
iex> selections(1..3, 2) |> Enum.to_list
[[1, 1], [1, 2], [1, 3], [2, 1], [2, 2], [2, 3], [3, 1], [3, 2], [3, 3]]
iex> selections([1, 1, 2], 2) |> Enum.to_list
[[1, 1], [1, 2], [2, 1], [2, 2]]@spec subsets(Enum.t()) :: SComb.Sequence.t()
Returns a lazy SComb.Sequence containing all sets possible with any
combination of elements in enum.
Examples
iex> subsets(1..3) |> Enum.to_list
[[], [1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3]]
iex> subsets([1, 1, 2]) |> Enum.to_list
[[], [1], [2], [1, 1], [1, 2], [1, 1, 2]]