bytezen · June 22, 2017 21:11 · Jul 13, 2016 · Jul 13, 2016 · Jul 12, 2016 · Apr 3, 2016
diff --git a/permutations.js b/permutations.js
@@ -1,6 +1,21 @@
 /**
  * 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')
 
@@ -124,11 +139,3 @@ function combinations_with_replacement(obj,n){
 }
 
 module.exports={combinations_with_replacement,combinations,product,permutations}
-
-// 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)
diff --git a/permutations.js b/permutations.js
@@ -1,4 +1,7 @@
-
+/**
+ * Lodash mixins for combinatorics
+ * Inspired by python itertools: https://docs.python.org/2.7/library/itertools.html
+ */
 var _ = require('lodash')
 
 /**
@@ -37,7 +40,6 @@ function _cartesianProductObj(optObj){
 /**
  * Generate the cartesian product of input objects, arrays, or strings
  *
- * 
  *
  * product('me','hi')
  * // => [["m","h"],["m","i"],["e","h"],["e","i"]]
@@ -62,33 +64,36 @@ function product(opts){
 }
 
 /**
- * Generate permutations
- * 
+ * Generate permutations, in all possible orderings, with no repeat values
+ *
  *
  * permutations([1,2,3],2)
- * // => [[1,1],[1,2],[1,3],[2,1],[2,2],[2,3],[3,1],[3,2],[3,3]]
+ * // => [[1,2],[1,3],[2,1],[2,3],[3,1],[3,2]
  *
  * permutations('cat',2)
- * // => [["c","c"],["c","a"],["c","t"],["a","c"],["a","a"],["a","t"],["t","c"],["t","a"],["t","t"]]
+ * // => [["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
+    // make n copies of keys/indices
     for (var j = 0, nInds=[]; j < n; j++) {nInds.push(_.keys(obj)) }
-    return _.map(product(nInds),indices=>_.map(indices,i=>obj[i]))
+    // 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 combinations of an object
- * 
+ * Generate n combinations of an object with no repeat values in each combination.
+ *
  *
  * 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]]
+ * // => [[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);
@@ -101,6 +106,24 @@ function combinations(obj,n){
         .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}
 
 // product('me','hi')
 // product({who:['me','you'],say:['hi','by']})

diff --git a/permutations.test.js b/permutations.test.js
@@ -1,6 +1,6 @@
 // mocha unit tests
 import {expect} from 'chai'
-import {combinations,product,permutations} from './products'
+import {combinations,product,permutations,combinations_with_replacement} from './products'
 
 describe('products', function () {
     describe('product', function () {
@@ -23,16 +23,22 @@ describe('products', function () {
     })
     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]])
+            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,1],[1,2],[1,3],[2,1],[2,2],[2,3],[3,1],[3,2],[3,3]])
+                .eql([[1,2],[1,3],[2,1],[2,3],[3,1],[3,2]])
             expect(permutations('cat',2))
-                .eql([["c","c"],["c","a"],["c","t"],["a","c"],["a","a"],["a","t"],["t","c"],["t","a"],["t","t"]])
+                .eql([["c","a"],["c","t"],["a","c"],["a","t"],["t","c"],["t","a"]])
         });
 
     })

diff --git a/permutations.js b/permutations.js
@@ -22,8 +22,8 @@ function _cartesianProductOf(args) {
 }
 
 /** Generate all combination of arguments from objects
-  * @param {Object} opts    - An object or arrays with keys describing options  {firstName:['Ben','Jade','Darren'],lastName:['Smith','Miller']}
-  * @returns {Array}        - An array of objects e.g. [{firstName:'Ben',LastName:'Smith'},{..]
+  *  {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);
@@ -37,7 +37,7 @@ function _cartesianProductObj(optObj){
 /**
  * Generate the cartesian product of input objects, arrays, or strings
  *
- * @example
+ * 
  *
  * product('me','hi')
  * // => [["m","h"],["m","i"],["e","h"],["e","i"]]
@@ -63,7 +63,7 @@ function product(opts){
 
 /**
  * Generate permutations
- * @example
+ * 
  *
  * permutations([1,2,3],2)
  * // => [[1,1],[1,2],[1,3],[2,1],[2,2],[2,3],[3,1],[3,2],[3,3]]
@@ -83,7 +83,7 @@ function permutations(obj, n){
 
 /**
  * Generate combinations of an object
- * @example
+ * 
  *
  * 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]]

diff --git a/permutations.test.js b/permutations.test.js
@@ -0,0 +1,39 @@
+// 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"]])
+        });
+
+    })
+})
diff --git a/permutations.js b/permutations.js
@@ -53,8 +53,10 @@ function _cartesianProductObj(optObj){
  * // => [["m","h"],["m","i"],["e","h"],["e","i"]]
  */
 function product(opts){
-    if (arguments.length===1 && (!_.isArray(opts)))
+    if (arguments.length===1 && !_.isArray(opts))
         return _cartesianProductObj(opts)
+    else if (arguments.length===1)
+        return _cartesianProductOf(opts)
     else
         return _cartesianProductOf(arguments)
 }

diff --git a/cartesianProduct.js → permutations.js b/cartesianProduct.js → permutations.js
@@ -1,5 +1,5 @@
 
-import _ from 'lodash'
+var _ = require('lodash')
 
 /**
  * Generate all combination of arguments when given arrays or strings
@@ -52,14 +52,58 @@ function _cartesianProductObj(optObj){
  * product(['me','hi'])
  * // => [["m","h"],["m","i"],["e","h"],["e","i"]]
  */
-export function product(opts){
-    if (arguments.length==1 && !_.isArray(opts))
+function product(opts){
+    if (arguments.length===1 && (!_.isArray(opts)))
         return _cartesianProductObj(opts)
     else
-        return _cartesianProductOf(opts)
+        return _cartesianProductOf(arguments)
 }
 
+/**
+ * Generate permutations
+ * @example
+ *
+ * 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
+ * @example
+ *
+ * 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({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)
diff --git a/cartesianProduct.js b/cartesianProduct.js
@@ -1,28 +1,65 @@
-    /** Generate all combination of arguments from array using functional programming instead of recursive
-    * @param {Object} opts    - An array or arrays with keys describing options  [['Ben','Jade','Darren'],['Smith','Miller']]
-    * @returns {Array}        - An array of arrays e.g. [['Ben','Smith'],[..]]
-    **/
-    function cartesianProductOf(opts) {
-        if (arguments.length>1) opts=arguments;
-        return _.reduce(opts, function(a, b) {
-            return _.flatten(_.map(a, function(x) {
-                return _.map(b, function(y) {
-                    return x.concat([y]);
-                });
-            }), true);
-        }, [ [] ]);
-    };
 
+import _ from 'lodash'
 
-    /** Generate all combination of arguments from objects using functional programming instead of recursive
-      * @param {Object} opts    - An object or arrays with keys describing options  {firstName:['Ben','Jade','Darren'],lastName:['Smith','Miller']}
-      * @returns {Array}        - An array of objects e.g. [{firstName:'Ben',LastName:'Smith'},{..]
-      **/
-    function cartesianProductObj(optObj){
-        var opts = _.values(optObj);
-        var keys = _.keys(optObj);
-        var combs = cartesianProductOf(opts);
-        return _.map(combs,function(comb){
-            return _.zipObject(keys,comb);
-        });
-    }
+/**
+ * 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
+  * @param {Object} opts    - An object or arrays with keys describing options  {firstName:['Ben','Jade','Darren'],lastName:['Smith','Miller']}
+  * @returns {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
+ *
+ * @example
+ *
+ * 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"]]
+ */
+export function product(opts){
+    if (arguments.length==1 && !_.isArray(opts))
+        return _cartesianProductObj(opts)
+    else
+        return _cartesianProductOf(opts)
+}
+
+// product('me','hi')
+// product({who:['me','you'],say:['hi','by']})
+// product({who:['me','you'],say:['hi','by']})
+// product(['me','hi'])
diff --git a/cartesianProduct.js b/cartesianProduct.js
@@ -0,0 +1,28 @@
+    /** Generate all combination of arguments from array using functional programming instead of recursive
+    * @param {Object} opts    - An array or arrays with keys describing options  [['Ben','Jade','Darren'],['Smith','Miller']]
+    * @returns {Array}        - An array of arrays e.g. [['Ben','Smith'],[..]]
+    **/
+    function cartesianProductOf(opts) {
+        if (arguments.length>1) opts=arguments;
+        return _.reduce(opts, function(a, b) {
+            return _.flatten(_.map(a, function(x) {
+                return _.map(b, function(y) {
+                    return x.concat([y]);
+                });
+            }), true);
+        }, [ [] ]);
+    };
+
+
+    /** Generate all combination of arguments from objects using functional programming instead of recursive
+      * @param {Object} opts    - An object or arrays with keys describing options  {firstName:['Ben','Jade','Darren'],lastName:['Smith','Miller']}
+      * @returns {Array}        - An array of objects e.g. [{firstName:'Ben',LastName:'Smith'},{..]
+      **/
+    function cartesianProductObj(optObj){
+        var opts = _.values(optObj);
+        var keys = _.keys(optObj);
+        var combs = cartesianProductOf(opts);
+        return _.map(combs,function(comb){
+            return _.zipObject(keys,comb);
+        });
+    }