acarl005 / generatorics

An efficient combinatorics library for JavaScript utilizing ES2015 generators.

Generatorics

An efficient combinatorics library for JavaScript utilizing ES2015 generators. Generate combinations, permutations, and power sets of arrays or strings.

• Node

npm install generatorics

var G = require('generatorics');

• Browser

bower install generatorics

<script src="file/path/to/generatorics.js"></script>

Note: This module is not transpiled for compatibility, as it degrades the performance. Check your browser/node version.

Usage

power set

for (var subset of G.powerSet(['a', 'b', 'c'])) {
  console.log(subset);
}
// [ ]
// [ 'a' ]
// [ 'a', 'b' ]
// [ 'a', 'b', 'c' ]
// [ 'a', 'c' ]
// [ 'b' ]
// [ 'b', 'c' ]
// [ 'c' ]

permutation

for (var perm of G.permutation(['a', 'b', 'c'], 2)) {
  console.log(perm);
}
// [ 'a', 'b' ]
// [ 'a', 'c' ]
// [ 'b', 'a' ]
// [ 'b', 'c' ]
// [ 'c', 'a' ]
// [ 'c', 'b' ]

for (var perm of G.permutation(['a', 'b', 'c'])) { // assumes full length of array
  console.log(perm);
}
// [ 'a', 'b', 'c' ]
// [ 'a', 'c', 'b' ]
// [ 'b', 'a', 'c' ]
// [ 'b', 'c', 'a' ]
// [ 'c', 'b', 'a' ]
// [ 'c', 'a', 'b' ]

combination

for (var comb of G.combination(['a', 'b', 'c'], 2)) {
  console.log(comb);
}
// [ 'a', 'b' ]
// [ 'a', 'c' ]
// [ 'b', 'c' ]

For efficiency, each array being yielded is the same one being mutated on each iteration. DO NOT mutate the array.

var combs = [];
for (var comb of G.combination(['a', 'b', 'c'], 2)) {
  combs.push(comb);
}
console.log(combs);
// [ [ 'b', 'c' ], [ 'b', 'c' ], [ 'b', 'c' ] ]

You can clone if necessary, or use the clone submodule

permutation of combination

for (var perm of G.permutationCombination(['a', 'b', 'c'])) {
  console.log(perm);
}
// [ ]
// [ 'a' ]
// [ 'a', 'b' ]
// [ 'a', 'b', 'c' ]
// [ 'a', 'c' ]
// [ 'a', 'c', 'b' ]
// [ 'b' ]
// [ 'b', 'a' ]
// [ 'b', 'a', 'c' ]
// [ 'b', 'c' ]
// [ 'b', 'c', 'a' ]
// [ 'c' ]
// [ 'c', 'a' ]
// [ 'c', 'a', 'b' ]
// [ 'c', 'b' ]
// [ 'c', 'b', 'a' ]

cartesian product

for (var prod of G.cartesian([0, 1, 2], [0, 10, 20], [0, 100, 200])) {
  console.log(prod);
}
// [ 0, 0, 0 ],  [ 0, 0, 100 ],  [ 0, 0, 200 ]
// [ 0, 10, 0 ], [ 0, 10, 100 ], [ 0, 10, 200 ]
// [ 0, 20, 0 ], [ 0, 20, 100 ], [ 0, 20, 200 ]
// [ 1, 0, 0 ],  [ 1, 0, 100 ],  [ 1, 0, 200 ]
// [ 1, 10, 0 ], [ 1, 10, 100 ], [ 1, 10, 200 ]
// [ 1, 20, 0 ], [ 1, 20, 100 ], [ 1, 20, 200 ]
// [ 2, 0, 0 ],  [ 2, 0, 100 ],  [ 2, 0, 200 ]
// [ 2, 10, 0 ], [ 2, 10, 100 ], [ 2, 10, 200 ]
// [ 2, 20, 0 ], [ 2, 20, 100 ], [ 2, 20, 200 ]

base N

for (var num of G.baseN(['a', 'b', 'c'])) {
  console.log(num);
}
// [ 'a', 'a', 'a' ], [ 'a', 'a', 'b' ], [ 'a', 'a', 'c' ]
// [ 'a', 'b', 'a' ], [ 'a', 'b', 'b' ], [ 'a', 'b', 'c' ]
// [ 'a', 'c', 'a' ], [ 'a', 'c', 'b' ], [ 'a', 'c', 'c' ]
// [ 'b', 'a', 'a' ], [ 'b', 'a', 'b' ], [ 'b', 'a', 'c' ]
// [ 'b', 'b', 'a' ], [ 'b', 'b', 'b' ], [ 'b', 'b', 'c' ]
// [ 'b', 'c', 'a' ], [ 'b', 'c', 'b' ], [ 'b', 'c', 'c' ]
// [ 'c', 'a', 'a' ], [ 'c', 'a', 'b' ], [ 'c', 'a', 'c' ]
// [ 'c', 'b', 'a' ], [ 'c', 'b', 'b' ], [ 'c', 'b', 'c' ]
// [ 'c', 'c', 'a' ], [ 'c', 'c', 'b' ], [ 'c', 'c', 'c' ]

Clone Submodule

Each array yielded from the generator is actually the same array in memory, just mutated to have different elements. This is to avoid the unnecessary creation of a bunch of arrays, which consume memory. As a result, you get a strange result when trying to generate an array.

var combs = G.combination(['a', 'b', 'c'], 2);
console.log([...combs]);
// [ [ 'b', 'c' ], [ 'b', 'c' ], [ 'b', 'c' ] ]

Instead, you can use the clone submodule.

var combs = G.clone.combination(['a', 'b', 'c'], 2);
console.log([...combs]);
// [ [ 'a', 'b' ], [ 'a', 'c' ], [ 'b', 'c' ] ]

G.clone

This submodule produces generators that yield a different array on each iteration in case you need to mutate it. The combination, permutation, powerSet, permutationCombination, baseN, baseNAll, and cartesian methods are provided on this submodule.

Cool things to do with ES2015 generators

var combs = G.clone.combination([1, 2, 3], 2);

// "for-of" loop
for (let comb of combs) {
  console.log(comb);
}

// generate arrays
Array.from(combs);
[...combs];

// generate sets
new Set(combs);

// spreading in function calls
console.log(...combs);

Writing a code generator? Need to produce an infinite stream of minified variable names?

No problem! Just pass in a collection of all your valid characters and start generating.

var mininym = G.baseNAll('abcdefghijklmnopqrstuvwxyz$#')
var name = mininym.next().value.join('')
global[name] = 'some value'

Card games anyone?

var cards = [...G.clone.cartesian('♠♥♣♦', 'A23456789JQK')];
console.log(G.shuffle(cards));
// [ [ '♦', '6' ], [ '♠', '6' ], [ '♣', '7' ], [ '♥', 'K' ],
//   [ '♣', 'J' ], [ '♥', '4' ], [ '♦', '2' ], [ '♥', '9' ],
//   [ '♦', 'Q' ], [ '♠', 'Q' ], [ '♠', '4' ], [ '♠', 'K' ],
//   [ '♥', '3' ], [ '♥', '7' ], [ '♠', '5' ], [ '♦', '7' ],
//   [ '♥', '5' ], [ '♣', 'Q' ], [ '♣', '9' ], [ '♠', 'A' ],
//   [ '♣', '4' ], [ '♣', '3' ], [ '♥', 'A' ], [ '♥', '8' ],
//   [ '♣', '8' ], [ '♦', '8' ], [ '♠', '8' ], [ '♣', '5' ],
//   [ '♥', '2' ], [ '♥', 'Q' ], [ '♦', 'A' ], [ '♥', '6' ],
//   [ '♠', '2' ], [ '♣', '6' ], [ '♠', '3' ], [ '♦', 'K' ],
//   [ '♦', 'J' ], [ '♠', '7' ], [ '♥', 'J' ], [ '♦', '5' ],
//   [ '♦', '9' ], [ '♦', '3' ], [ '♠', '9' ], [ '♣', '2' ],
//   [ '♣', 'A' ], [ '♣', 'K' ], [ '♦', '4' ], [ '♠', 'J' ] ]

Documentation

G

• G
  • .factorial(n) ⇒ Number
  • .factoradic(n) ⇒ Array
  • .P(n, k) ⇒ Number
  • .C(n, k) ⇒ Number
  • .choices(n, k, [options]) ⇒ Number
  • .combination(arr, [size]) ⇒ Generator
  • .permutation(arr, [size]) ⇒ Generator
  • .powerSet(arr) ⇒ Generator
  • .permutationCombination(arr) ⇒ Generator
  • .baseN(arr, [size]) ⇒ Generator
  • .baseNAll(arr) ⇒ Generator
  • .cartesian(...sets) ⇒ Generator
  • .shuffle(arr) ⇒ Array

G.factorial(n) ⇒ Number

Calculates a factorial

Kind: static method of G
Returns: Number - n!

Param	Type	Description
n	Number	The number to operate the factorial on.

G.factoradic(n) ⇒ Array

Converts a number to the factorial number system. Digits are in least significant order.

Kind: static method of G
Returns: Array - digits of n in factoradic in least significant order

Param	Type	Description
n	Number	Integer in base 10

G.P(n, k) ⇒ Number

Calculates the number of possible permutations of "k" elements in a set of size "n".

Kind: static method of G
Returns: Number - n P k

Param	Type	Description
n	Number	Number of elements in the set.
k	Number	Number of elements to choose from the set.

G.C(n, k) ⇒ Number

Calculates the number of possible combinations of "k" elements in a set of size "n".

Kind: static method of G
Returns: Number - n C k

Param	Type	Description
n	Number	Number of elements in the set.
k	Number	Number of elements to choose from the set.

G.choices(n, k, [options]) ⇒ Number

Higher level method for counting number of possible combinations of "k" elements from a set of size "n".

Kind: static method of G
Returns: Number - Number of possible combinations.

Param	Type	Description
n	Number	Number of elements in the set.
k	Number	Number of elements to choose from the set.
[options]	Object
options.replace	Boolean	Is replacement allowed after each choice?
options.ordered	Boolean	Does the order of the choices matter?

G.combination(arr, [size]) ⇒ Generator

Generates all combinations of a set.

Kind: static method of G
Returns: Generator - yields each combination as an array

Param	Type	Default	Description
arr	Array | String		The set of elements.
[size]	Number	arr.length	Number of elements to choose from the set.

G.permutation(arr, [size]) ⇒ Generator

Generates all permutations of a set.

Kind: static method of G
Returns: Generator - yields each permutation as an array

Param	Type	Default	Description
arr	Array | String		The set of elements.
[size]	Number	arr.length	Number of elements to choose from the set.

G.powerSet(arr) ⇒ Generator

Generates all possible subsets of a set (a.k.a. power set).

Kind: static method of G
Returns: Generator - yields each subset as an array

Param	Type	Description
arr	Array | String	The set of elements.

G.permutationCombination(arr) ⇒ Generator

Generates the permutation of the combinations of a set.

Kind: static method of G
Returns: Generator - yields each permutation as an array

Param	Type	Description
arr	Array | String	The set of elements.

G.baseN(arr, [size]) ⇒ Generator

Generates all possible "numbers" from the digits of a set.

Kind: static method of G
Returns: Generator - yields all digits as an array

Param	Type	Default	Description
arr	Array | String		The set of digits.
[size]	Number	arr.length	How many digits will be in the numbers.

G.baseNAll(arr) ⇒ Generator

Infinite generator for all possible "numbers" from a set of digits.

Kind: static method of G
Returns: Generator - yields all digits as an array

Param	Type	Description
arr	Array | String	The set of digits

G.cartesian(...sets) ⇒ Generator

Generates the cartesian product of the sets.

Kind: static method of G
Returns: Generator - yields each product as an array

Param	Type	Description
...sets	Array | String	variable number of sets of n elements.

G.shuffle(arr) ⇒ Array

Shuffles an array in place using the Fisher–Yates shuffle.

Kind: static method of G
Returns: Array - a random, unbiased perutation of arr

Param	Type	Description
arr	Array	A set of elements.

generatorics's Issues

Functions should be bound to context or not use this

Hello @acarl005. The fact that your functions need this to function has this somewhat uncomfortable side-effect that you cannot use them without calling them from the generatorics object.

Here is what I mean:

// If you do the following for instance:
var combination = require('generatorics').combination;

// This will throw & fail because the function does not have the required scope
combination([1, 2, 3], 2);

A solution would be to bind your function to the correct scope before exporting or rewrite the code marginally not to rely on the scope of the generatorics object.

Permutation not work if size is higher than the number of elements in the set

Hello,

The permutation function doesn't work if the parameter size is higher than the length of the parameter arr.
Example

Works

G.permutation(['0', '1', '2', '3'], 4);

Doesn't work

G.permutation(['0', '1', '2', '3'], 5);

Using standard iterators

Hello @acarl005. Thanks for the awesome library. Would you consider switching from generators (using the yield keyword) to basic JS iterators (just the object with the next function & following JS iterator protocol) so that it remains possible to use your library with more old-school JS engines (+ attaching Symbol.iterator so that your API remains totally unchanged)?

I could help you achieve that by recoding the necessary parts if you'd like.

As a side note, I am wondering whether you attempted to benchmark generators vs. iterator protocol and if you went for generators for obvious performance reasons I missed.

Have a good day.

TypeScript definitions

Please add typescript definitions (or rewrite in TypeScript), so we can have strong typing, compilation checks and IDE code completion support.

Skipping permutations

Hi!
In some problems, skipping permutations that does not solve the problem is an effective optimization. Would it be possible to add skipping of permutations?

Example:

for (let perm of G.permutations([1,2,3,4,5])) {
  if (shouldSkip(perm)) {
    // "increments" element at position 1
    G.incrementElement(1);
    // given perm == [1, 2, 3, 4, 5], 
    // 2 is at index 1,
    // next permutations will be [1, 3, 2, 4, 5]
  }
  if (isSolution(perm)) {
    break;
  }
}

function shouldSkip (perm) {
  // we know somehow that any permutations starting
  // with 1 and 2 will not solve the problem
  // e.g. none of these will solve the problem: [1,2,3,4,5], [1,2,3,4,5], [1,2,4,3,5] ....
  return perm[0] === 1 && perm[1] === 2;
}

PS: I've not looked into the code, but will take a grab at it if this sounds like a reasonable addition.