Simple combinatorics like power set, combination, and permutation in JavaScript
<script src="combinatorics.js"></script>
var Combinatorics = require('./combinatorics.js').Combinatorics;
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"]
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"]
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"]
]
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]
]
- .
P(m, n)
calculates m P n - .
C(m, n)
calculates m C n - .
factorial(n)
calculatesn!
- .
factoradic(n)
returns the factoradic representation of n in array, LSB ORDER. See http://en.wikipedia.org/wiki/Factorial_number_system
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.
Creates a generator which generates the power set of ary
Creates a generator which generates the combination of ary with nelem elements. When nelem is ommited, ary.length is used.
Creates a generator which generates the permutation of ary with nelem elements. When nelem is ommited, ary.length is used.
Creates a generator which generates the cartesian product of the arrays. All arguments must be arrays with more than one element.
All generators have following methods:
Returns the element or undefined
if no more element is available.
Applies the callback function for each element.
All elements at once.
All elements at once with function f applied to each element.
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;
});
};
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.
Same as generator.length
Available for power
and cartesianProduct
generator which returns the nth element.
Available for cartesianProduct
generator. Arguments are coordinates in integer.
Arguments can be out of bounds but it returns undefined
in such cases.