# `SComb`
[🔗](https://github.com/tallakt/scomb/blob/v0.3.0/lib/scomb.ex#L1)

# 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`](https://hexdocs.pm/elixir/Stream.html), 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"}
      ]
    end

## Examples

### 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])
    6

### Permuted 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)
    3

### Cartesian 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
    50

## Development

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](https://github.com/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

# `cartesian_product`

```elixir
@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
    [[]]

# `cartesian_product`

```elixir
@spec cartesian_product(Enum.t(), Enum.t()) :: [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]]

# `combinations`

```elixir
@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]]

# `combinations_with_replacement`

```elixir
@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]]

# `count_cartesian_product`

```elixir
@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

# `count_combinations`

```elixir
@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

# `count_combinations_with_replacement`

```elixir
@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

# `count_partitions`

```elixir
@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

# `count_permutations`

```elixir
@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

# `count_permuted_combinations`

```elixir
@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

# `count_selections`

```elixir
@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

# `count_subsets`

```elixir
@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])
    6

# `drop_permutations`

```elixir
@spec drop_permutations(Enum.t(), integer()) :: Enum.t()
```

Calculates 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]]

# `nth_cartesian_product`

```elixir
@spec nth_cartesian_product([Enum.t()], integer()) :: list() | no_return()
```

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]

# `nth_combination`

```elixir
@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]

# `nth_combination_with_replacement`

```elixir
@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]

# `nth_partition`

```elixir
@spec nth_partition(Enum.t(), integer()) :: [list()] | no_return()
```

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

# `nth_permutation`

```elixir
@spec nth_permutation(Enum.t(), integer()) :: list() | no_return()
```

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]

# `nth_permuted_combination`

```elixir
@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]

# `nth_selection`

```elixir
@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]

# `nth_subset`

```elixir
@spec nth_subset(Enum.t(), integer()) :: list() | no_return()
```

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]

# `partitions`

```elixir
@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

# `permutation_index`

```elixir
@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]

# `permutations`

```elixir
@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]]

# `permuted_combinations`

```elixir
@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]]

# `selections`

```elixir
@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]]

# `subsets`

```elixir
@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]]

---

*Consult [api-reference.md](api-reference.md) for complete listing*