combinatorial-generators
v1.1.2
Published
Combinatorial generators including combinations, permutations, combinations with replacement, permutations with replacement, cartesian products, and power sets.
Downloads
4,487
Maintainers
Readme
combinatorics
This module provides generators for iterating subsets of an input. It is heavily
inspired by the combinatorial iterators provided by the
itertools package from the
Python
standard library.
- All generators are importable on their own.
- These implementations do not build up intermediate results in memory.
- All functions iterate subsets lexicographically according to their input indices. If the input is sorted the output will be too.
- Likewise, whether the input elements are unique or not does not matter.
- The inputs provided are not modified, however, consumable iterables will be consumed.
Usage
combinations
Yields r
length Arrays
from the input iterable
. Order of selection does
not matter and elements are chosen without replacement.
import { assertEquals } from "asserts";
import { combinations } from "combinatorial-generators";
const sequences = [...combinations([1, 2, 3, 4], 2)];
assertEquals(sequences, [
[1, 2],
[1, 3],
[1, 4],
[2, 3],
[2, 4],
[3, 4],
]);
permutations
Yields r
length Arrays
from the input iterable
. Order of selection is
important and elements are chosen without replacement. If r
is undefined, then
the length of the iterable
is used.
import { assertEquals } from "asserts";
import { permutations } from "combinatorial-generators";
const sequences = [...permutations([1, 2, 3, 4], 2)];
assertEquals(sequences, [
[1, 2], [1, 3], [1, 4],
[2, 1], [2, 3], [2, 4],
[3, 1], [3, 2], [3, 4],
[4, 1], [4, 2], [4, 3],
]);
combinationsWithReplacement
Yields r
length Arrays
from the input iterable
. Order of selection is not
important and elements are chosen with replacement.
import { assertEquals } from "asserts";
import { combinationsWithReplacement } from "combinatorial-generators";
const sequences = [...combinationsWithReplacement([1, 2, 3, 4], 2)];
assertEquals(sequences, [
[1, 1],
[1, 2],
[1, 3],
[1, 4],
[2, 2],
[2, 3],
[2, 4],
[3, 3],
[3, 4],
[4, 4],
]);
permutationsWithReplacement
Yields r
length Arrays
from the input iterable
. Order of selection is
important and elements are chosen with replacement.
import { assertEquals } from "asserts";
import { permutationsWithReplacement } from "combinatorial-generators";
const sequences = [...permutationsWithReplacement([1, 2, 3, 4], 2)];
assertEquals(sequences, [
[1, 1], [1, 2], [1, 3], [1, 4],
[2, 1], [2, 2], [2, 3], [2, 4],
[3, 1], [3, 2], [3, 3], [3, 4],
[4, 1], [4, 2], [4, 3], [4, 4],
]);
cartesianProduct
Roughly equivalent to running nested for...of
loops using one of the inputs to
provide the element at each index for the yielded Array
.
import { assertEquals } from "asserts";
import { cartesianProduct } from "combinatorial-generators";
const sequences = [...cartesianProduct([1, 2, 3], [4, 5, 6], [7, 8, 9])];
assertEquals(sequences, [
[1, 4, 7], [1, 4, 8], [1, 4, 9],
[1, 5, 7], [1, 5, 8], [1, 5, 9],
[1, 6, 7], [1, 6, 8], [1, 6, 9],
[2, 4, 7], [2, 4, 8], [2, 4, 9],
[2, 5, 7], [2, 5, 8], [2, 5, 9],
[2, 6, 7], [2, 6, 8], [2, 6, 9],
[3, 4, 7], [3, 4, 8], [3, 4, 9],
[3, 5, 7], [3, 5, 8], [3, 5, 9],
[3, 6, 7], [3, 6, 8], [3, 6, 9],
]);
powerSet
The set of all subsets of the given iterable
. Equivalent to running
combinations
with 0 <= r <= iterable.length
and flattening the results. The
first subset is the empty set given when r = 0
.
import { assertEquals } from "asserts";
import { powerSet } from "combinatorial-generators";
const sequences = [...powerSet([1, 2, 3])];
assertEquals(sequences, [
[],
[1],
[2],
[3],
[1, 2],
[1, 3],
[2, 3],
[1, 2, 3],
]);