combinatorics.js

Simple combinatorics like power set, combination, and permutation in JavaScript

SYNOPSIS

In Browser

<script src="combinatorics.js"></script>

node.js

var Combinatorics = require('./combinatorics.js').Combinatorics;

Usage

power set

var cmb, a;
cmb = Combinatorics.power(['a','b','c']);
cmb.each(function(a){ console.log(a) });
//  []
//  ["a"]
//  ["b"]
//  ["a", "b"]
//  ["c"]
//  ["a", "c"]
//  ["b", "c"]
//  ["a", "b", "c"]

combination

cmb = Combinatorics.combination(['a','b','c','d'], 2);
while(a = cmb.next()) console.log(a);
//  ["a", "b"]
//  ["a", "c"]
//  ["a", "d"]
//  ["b", "c"]
//  ["b", "d"]
//  ["c", "d"]

permutation

cmb = Combinatorics.permutation(['a','b','c','d']); // assumes 4
console.log(cmb.toArray());
//  [
  ["a","b","c","d"],["a","b","d","c"],["a","c","b","d"],["a","c","d","b"],
  ["a","d","b","c"],["a","d","c","b"],["b","a","c","d"],["b","a","d","c"],
  ["b","c","a","d"],["b","c","d","a"],["b","d","a","c"],["b","d","c","a"],
  ["c","a","b","d"],["c","a","d","b"],["c","b","a","d"],["c","b","d","a"],
  ["c","d","a","b"],["c","d","b","a"],["d","a","b","c"],["d","a","c","b"],
  ["d","b","a","c"],["d","b","c","a"],["d","c","a","b"],["d","c","b","a"]
]

permutation of combination

cmb = Combinatorics.permutationCombination(['a','b','c']);
console.log(cmb.toArray());
// [
  [ 'a' ],
  [ 'b' ],
  [ 'c' ],
  [ 'a', 'b' ],
  [ 'b', 'a' ],
  [ 'a', 'c' ],
  [ 'c', 'a' ],
  [ 'b', 'c' ],
  [ 'c', 'b' ],
  [ 'a', 'b', 'c' ],
  [ 'a', 'c', 'b' ],
  [ 'b', 'a', 'c' ],
  [ 'b', 'c', 'a' ],
  [ 'c', 'a', 'b' ],
  [ 'c', 'b', 'a' ] ]

cartesian product

cp = Combinatorics.cartesianProduct([0, 1, 2], [0, 10, 20], [0, 100, 200]);
console.log(cp.toArray());
//  [
  [0, 0, 0],   [1, 0, 0],   [2, 0, 0],
  [0, 10, 0],  [1, 10, 0],  [2, 10, 0],
  [0, 20, 0],  [1, 20, 0],  [2, 20, 0],
  [0, 0, 100], [1, 0, 100], [2, 0, 100],
  [0, 10, 100],[1, 10, 100],[2, 10, 100],
  [0, 20, 100],[1, 20, 100],[2, 20, 100],
  [0, 0, 200], [1, 0, 200], [2, 0, 200],
  [0, 10, 200],[1, 10, 200],[2, 10, 200],
  [0, 20, 200],[1, 20, 200],[2, 20, 200]
]

base N

baseN = Combinatorics.baseN(['a','b','c'], 3);
console.log(baseN.toArray())
// [
  [ 'a', 'a', 'a' ],
  [ 'b', 'a', 'a' ],
  [ 'c', 'a', 'a' ],
  [ 'a', 'b', 'a' ],
  [ 'b', 'b', 'a' ],
  [ 'c', 'b', 'a' ],
  [ 'a', 'c', 'a' ],
  [ 'b', 'c', 'a' ],
  [ 'c', 'c', 'a' ],
  [ 'a', 'a', 'b' ],
  [ 'b', 'a', 'b' ],
  [ 'c', 'a', 'b' ],
  [ 'a', 'b', 'b' ],
  [ 'b', 'b', 'b' ],
  [ 'c', 'b', 'b' ],
  [ 'a', 'c', 'b' ],
  [ 'b', 'c', 'b' ],
  [ 'c', 'c', 'b' ],
  [ 'a', 'a', 'c' ],
  [ 'b', 'a', 'c' ],
  [ 'c', 'a', 'c' ],
  [ 'a', 'b', 'c' ],
  [ 'b', 'b', 'c' ],
  [ 'c', 'b', 'c' ],
  [ 'a', 'c', 'c' ],
  [ 'b', 'c', 'c' ],
  [ 'c', 'c', 'c' ]
]

Arithmetic Functions

• .P(m, n) calculates m P n
• .C(m, n) calculates m C n
• .factorial(n) calculates n!
• .factoradic(n) returns the factoradic representation of n in array, in least significant order. See http://en.wikipedia.org/wiki/Factorial_number_system

DESCRIPTION

All methods create generators. Instead of creating all elements at once, each element is created on demand. So it is memory efficient even when you need to iterate through millions of elements.

Combinatorics.power( ary )

Creates a generator which generates the power set of ary

Combinatorics.combination( ary , nelem )

Creates a generator which generates the combination of ary with nelem elements. When nelem is ommited, ary.length is used.

Combinatorics.permutation( ary, nelem )

Creates a generator which generates the permutation of ary with nelem elements. When nelem is ommited, ary.length is used.

Combinatorics.permutationCombination( ary)

Creates a generator which generates the permutation of the combination of ary. Equivalent to Combinatorics.permutation(Combinatorics.combination(ary)) but more efficient.

Combinatorics.cartesianProduct( ary0, ...)

Creates a generator which generates the cartesian product of the arrays. All arguments must be arrays with more than one element.

Combinatorics.baseN( ary , nelem )

Creates a generator which generates nelem -digit "numbers" where each digit is element in ary . Note this "number" is in least significant order.

When nelem is ommited, ary.length is used.

Generator Methods

All generators have following methods:

.next()

Returns the element or undefined if no more element is available.

.forEach(function(a){ ... });

Applies the callback function for each element.

.toArray()

All elements at once.

.map(function(a){ ... })

All elements at once with function f applied to each element.

.filter(function(a){ ... })

Returns an array with elements that passes the filter function. For example, you can redefine combination as follows:

myCombination = function(ary, n) {
  return Combinatorics.power(ary).filter(function (a) {
    return a.length === n;
  });
};

.length

Returns the number of elements to be generated Which equals to generator.toArray().length but it is precalculated without actually generating elements. Handy when you prepare for large iteraiton.

0 + generator

Same as generator.length

.nth(n)

Returns the nth element (starting 0). Available for power, cartesianProduct and baseN.

.get(x0, ...)

Available for cartesianProduct generator. Arguments are coordinates in integer. Arguments can be out of bounds but it returns undefined in such cases.