js-combinatorics

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

SYNOPSIS

In Browser

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

node.js

var Combinatorics = require('js-combinatorics');

Meteor

In your project directory:

meteor add jandres:js-combinatorics

Combinatorics is now available in your app/package namespace.

Usage

power set

var cmb, a;
cmb = Combinatorics.power(['a','b','c']);
cmb.forEach(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"]

bigCombination

This option may be a little slower and use a little more memory but can handle a much larger array

cmb = Combinatorics.bigCombination([1,2,3, ... ,35], 2);
while(a = cmb.next()) console.log(a);
//  ["1", "2"]
//  ["1", "3"]
//  ...
//  ["1", "32"]
//  ["2", "3"]
//  ...
//  ["2", "32"]

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. ary must be less than 31 in length, for larger ary use bigCombination

Combinatorics.bigCombination( 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.

.lazyMap(function(a){ ... })

A lazy (late execution) version of map. Adds a map function that is applied to each element when .next() is called. This doesn't reset the current progress (call init). Please call init after calling this if you want to reset your progress.

.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;
  });
};

.find(function(a){ ... })

Returns the first element that passes the filter function, or undefined if none matches. Same as .filter(f)[0] but faster.

.lazyFilter(function(a){ ... })

A lazy (late execution) version of filter. Adds a filter that runs when .next() is called and filters out results that don't match the supplied filter function. This doesn't reset the current progress (call init). Please call init after calling this if you want to reset your progress. For example, you can redefine combination as follows:

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

.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.