combinatorial-generators

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],
]);