Skip to content

Instantly share code, notes, and snippets.

@camwest
Forked from wassname/permutations.js
Created February 14, 2018 22:23
Show Gist options
  • Save camwest/6742707be4447b4ee390dd2661659169 to your computer and use it in GitHub Desktop.
Save camwest/6742707be4447b4ee390dd2661659169 to your computer and use it in GitHub Desktop.
Combinatorics permutatons and product in javascript using lodash.js (like python's itertools)
/**
* Lodash mixins for combinatorics
* Inspired by python itertools: https://docs.python.org/2.7/library/itertools.html
*
* Usage:
* permutations([0,1,2],2) // [[0,1],[0,2],[1,0],[1,2],[2,0],[2,1]]
* combinations([0,1,2],2) // [[0,1],[0,2],[1,2]]
* combinations_with_replacement([0,1,2],2)// [[0,0],[0,1],[0,2],[1,1],[1,2],[2,2]]
* product([0,1,2],[0,1,2]) // [[0,0],[0,1],[0,2],[1,0],[1,1],[1,2],[2,0],[2,1],[2,2]]
*
* Multiple input types:
* product('me','hi')
* product({who:['me','you'],say:['hi','by']})
* product(['me','you'],['hi','by'])
* product(['me','hi'])
* combinations([0,1,2,3],2)
* permutations([1,2,3],2)
* permutations('cat',2)
*/
var _ = require('lodash')
/**
* Generate all combination of arguments when given arrays or strings
* e.g. [['Ben','Jade','Darren'],['Smith','Miller']] to [['Ben','Smith'],[..]]
* e.g. 'the','cat' to [['t', 'c'],['t', 'a'], ...]
**/
function _cartesianProductOf(args) {
if (arguments.length>1) args=_.toArray(arguments);
// strings to arrays of letters
args=_.map(args, opt=>typeof opt==='string'?_.toArray(opt):opt)
return _.reduce(args, function(a, b) {
return _.flatten(_.map(a, function(x) {
return _.map(b, function(y) {
return _.concat(x,[y]);
});
}), true);
}, [ [] ]);
}
/** Generate all combination of arguments from objects
* {Object} opts - An object or arrays with keys describing options {firstName:['Ben','Jade','Darren'],lastName:['Smith','Miller']}
* {Array} - An array of objects e.g. [{firstName:'Ben',LastName:'Smith'},{..]
**/
function _cartesianProductObj(optObj){
var keys = _.keys(optObj);
var opts = _.values(optObj);
var combs = _cartesianProductOf(opts);
return _.map(combs,function(comb){
return _.zipObject(keys,comb);
});
}
/**
* Generate the cartesian product of input objects, arrays, or strings
*
*
* product('me','hi')
* // => [["m","h"],["m","i"],["e","h"],["e","i"]]
*
* product([1,2,3],['a','b','c']
* // => [[1,"a"],[1,"b"],[1,"c"],[2,"a"],[2,"b"],[2,"c"],[3,"a"],[3,"b"],[3,"c"]]
*
* product({who:['me','you'],say:['hi','by']})
* // => [{"who":"me","say":"hi"},{"who":"me","say":"by"},{"who":"you","say":"hi"},{"who":"you","say":"by"}]
*
* // It also takes in a single array of args
* product(['me','hi'])
* // => [["m","h"],["m","i"],["e","h"],["e","i"]]
*/
function product(opts){
if (arguments.length===1 && !_.isArray(opts))
return _cartesianProductObj(opts)
else if (arguments.length===1)
return _cartesianProductOf(opts)
else
return _cartesianProductOf(arguments)
}
/**
* Generate permutations, in all possible orderings, with no repeat values
*
*
* permutations([1,2,3],2)
* // => [[1,2],[1,3],[2,1],[2,3],[3,1],[3,2]
*
* permutations('cat',2)
* // => [["c","a"],["c","t"],["a","c"],["a","t"],["t","c"],["t","a"]]
*/
function permutations(obj, n){
if (typeof obj=='string') obj = _.toArray(obj)
n = n?n:obj.length
// make n copies of keys/indices
for (var j = 0, nInds=[]; j < n; j++) {nInds.push(_.keys(obj)) }
// get product of the indices, then filter to remove the same key twice
var arrangements = product(nInds).filter(pair=>pair[0]!==pair[1])
return _.map(arrangements,indices=>_.map(indices,i=>obj[i]))
}
/**
* Generate n combinations of an object with no repeat values in each combination.
*
*
* combinations([0,1,2,3],2)
* // => [[0,1],[0,2],[0,3],[1,2],[1,3],[2,3]]
*/
function combinations(obj,n){
/* filter out keys out of order, e.g. [0,1] is ok but [1,0] isn't */
function isSorted(arr) {
return _.every(arr, function (value, index, array) {
return index === 0 || String(array[index - 1]) <= String(value);
});
}
// array with n copies of the keys of obj
return _(permutations(_.keys(obj),n))
.filter(isSorted)
.map(indices=>_.map(indices,i=>obj[i]))
.value()
}
/**
* Generate n combinations with repeat values.
*
*
* combinations_with_replacement([0,1,2,3],2)
* // => [[0,0],[0,1],[0,2],[0,3],[1,1],[1,2],[1,3],[2,2],[2,3],[3,3]]
*/
function combinations_with_replacement(obj,n){
if (typeof obj=='string') obj = _.toArray(obj)
n = n?n:obj.length
// make n copies of keys/indices
for (var j = 0, nInds=[]; j < n; j++) {nInds.push(_.keys(obj)) }
// get product of the indices, then filter to keep elements in order
var arrangements = product(nInds).filter(pair=>pair[0]<=pair[1])
return _.map(arrangements,indices=>_.map(indices,i=>obj[i]))
}
module.exports={combinations_with_replacement,combinations,product,permutations}
// mocha unit tests
import {expect} from 'chai'
import {combinations,product,permutations,combinations_with_replacement} from './products'
describe('products', function () {
describe('product', function () {
it('should work for test data', function () {
expect(product('me','hi'))
.eql([["m","h"],["m","i"],["e","h"],["e","i"]])
expect(product(['me','hi']))
.eql([["m","h"],["m","i"],["e","h"],["e","i"]])
expect(product({who:['me','you'],say:['hi','by']}))
.eql([{"who":"me","say":"hi"},{"who":"me","say":"by"},{"who":"you","say":"hi"},{"who":"you","say":"by"}])
expect(product(['me','you'],['hi','by']))
.eql([["me","hi"],["me","by"],["you","hi"],["you","by"]])
})
})
describe('combinations', function () {
it('should work for test data', function () {
expect(combinations([1,2,3],2)).eql([[1,2],[1,3],[2,3]])
});
})
describe('combinations_with_replacement', function () {
it('should work for test data', function () {
expect(combinations_with_replacement([1,2,3],2)).eql([[1,1],[1,2],[1,3],[2,2],[2,3],[3,3]])
});
})
describe('permutations', function () {
it('should work for test data', function () {
expect(permutations([1,2,3],2))
.eql([[1,2],[1,3],[2,1],[2,3],[3,1],[3,2]])
expect(permutations('cat',2))
.eql([["c","a"],["c","t"],["a","c"],["a","t"],["t","c"],["t","a"]])
});
})
})
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment