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 = ;
- Browser
bower install generatorics
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 console;// [ ]// [ 'a' ]// [ 'a', 'b' ]// [ 'a', 'b', 'c' ]// [ 'a', 'c' ]// [ 'b' ]// [ 'b', 'c' ]// [ 'c' ]
permutation
for var perm of G console;// [ 'a', 'b' ]// [ 'a', 'c' ]// [ 'b', 'a' ]// [ 'b', 'c' ]// [ 'c', 'a' ]// [ 'c', 'b' ] for var perm of G // assumes full length of array console;// [ 'a', 'b', 'c' ]// [ 'a', 'c', 'b' ]// [ 'b', 'a', 'c' ]// [ 'b', 'c', 'a' ]// [ 'c', 'b', 'a' ]// [ 'c', 'a', 'b' ]
combination
for var comb of G console;// [ '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 combs;console;// [ [ 'b', 'c' ], [ 'b', 'c' ], [ 'b', 'c' ] ]
You can clone if necessary, or use the clone submodule
permutation of combination
for var perm of G console;// [ ]// [ '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 console;// [ 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 console;// [ '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;console;// [ [ 'b', 'c' ], [ 'b', 'c' ], [ 'b', 'c' ] ]
Instead, you can use the clone submodule.
var combs = Gclone;console;// [ [ '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 = Gclone; // "for-of" loopfor let comb of combs console; // generate arraysArray;...combs; // generate setscombs; // spreading in function callsconsole;
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 = Gvar name = mininymnextvalueglobalname = 'some value'
Card games anyone?
var cards = ...Gclone;console;// [ [ '♦', '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
- .factorial(n) ⇒
Number
G.factorial(n) ⇒ Calculates a factorial
Kind: static method of G
Returns: Number
- n!
Param | Type | Description |
---|---|---|
n | Number |
The number to operate the factorial on. |
Array
G.factoradic(n) ⇒ 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 |
Number
G.P(n, k) ⇒ 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. |
Number
G.C(n, k) ⇒ 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. |
Number
G.choices(n, k, [options]) ⇒ 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? |
Generator
G.combination(arr, [size]) ⇒ 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. |
Generator
G.permutation(arr, [size]) ⇒ 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. |
Generator
G.powerSet(arr) ⇒ 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. |
Generator
G.permutationCombination(arr) ⇒ 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. |
Generator
G.baseN(arr, [size]) ⇒ 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. |
Generator
G.baseNAll(arr) ⇒ 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 |
Generator
G.cartesian(...sets) ⇒ 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. |
Array
G.shuffle(arr) ⇒ 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. |