-
-
Save bytezen/a33b58d450a39f8e9ead47d63223c0d2 to your computer and use it in GitHub Desktop.
Combinatorics permutatons and product in javascript using lodash.js (like python's itertools)
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| 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 | |
| * | |
| * | |
| * permutations([1,2,3],2) | |
| * // => [[1,1],[1,2],[1,3],[2,1],[2,2],[2,3],[3,1],[3,2],[3,3]] | |
| * | |
| * permutations('cat',2) | |
| * // => [["c","c"],["c","a"],["c","t"],["a","c"],["a","a"],["a","t"],["t","c"],["t","a"],["t","t"]] | |
| */ | |
| function permutations(obj, n){ | |
| if (typeof obj=='string') obj = _.toArray(obj) | |
| n = n?n:obj.length | |
| // make n copies of keys | |
| for (var j = 0, nInds=[]; j < n; j++) {nInds.push(_.keys(obj)) } | |
| return _.map(product(nInds),indices=>_.map(indices,i=>obj[i])) | |
| } | |
| /** | |
| * Generate combinations of an object | |
| * | |
| * | |
| * combinations([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(obj,n){ | |
| 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() | |
| } | |
| // 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) |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| // mocha unit tests | |
| import {expect} from 'chai' | |
| import {combinations,product,permutations} 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,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,1],[1,2],[1,3],[2,1],[2,2],[2,3],[3,1],[3,2],[3,3]]) | |
| expect(permutations('cat',2)) | |
| .eql([["c","c"],["c","a"],["c","t"],["a","c"],["a","a"],["a","t"],["t","c"],["t","a"],["t","t"]]) | |
| }); | |
| }) | |
| }) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment