I have several numbers in an array

var numArr = [1, 3, 5, 9];

I want to cycle through that array and multiply every unique 3 number combination as follows:

1 * 3 * 5 = 
1 * 3 * 9 = 
1 * 5 * 9 = 
3 * 5 * 9 =

Then return an array of all the calculations

var ansArr = [15,27,45,135];

Anyone have an elegant solution? Thanks in advance.

I have several numbers in an array

var numArr = [1, 3, 5, 9];

I want to cycle through that array and multiply every unique 3 number combination as follows:

1 * 3 * 5 = 
1 * 3 * 9 = 
1 * 5 * 9 = 
3 * 5 * 9 =

Then return an array of all the calculations

var ansArr = [15,27,45,135];

Anyone have an elegant solution? Thanks in advance.

• javascript
• combinations

• 3 In the title you ask for permutations, but in the body you mention combinations. Which is it? (I'm guessing combinations, since multiplication is commutative.) – Marcelo Cantos Commented Oct 30, 2010 at 23:20
• 1 @DaveKingsnorth Note: You have strings in your array, not numbers. – Šime Vidas Commented Oct 30, 2010 at 23:25
• @Sime Vidas - That was a mistake, they should be numbers not strings – DaveKingsnorth Commented Oct 30, 2010 at 23:27
• 1 @DaveKingsnorth Are the numbers in the array distinct? – Šime Vidas Commented Oct 30, 2010 at 23:30
• @Sime Vidas - Not always, there could be duplicate numbers within the array – DaveKingsnorth Commented Oct 30, 2010 at 23:32

6 Answers 6

A general-purpose algorithm for generating combinations is as follows:

function combinations(numArr, choose, callback) {
    var n = numArr.length;
    var c = [];
    var inner = function(start, choose_) {
        if (choose_ == 0) {
            callback(c);
        } else {
            for (var i = start; i <= n - choose_; ++i) {
                c.push(numArr[i]);
                inner(i + 1, choose_ - 1);
                c.pop();
            }
        }
    }
    inner(0, choose);
}

In your case, you might call it like so:

function product(arr) {
    p = 1;
    for (var i in arr) {
        p *= arr[i];
    }
    return p;
}

var ansArr = [];

combinations(
    [1, 3, 5, 7, 9, 11], 3,
    function output(arr) {
        ansArr.push(product(arr));
    });

document.write(ansArr);

...which, for the given input, yields this:

15,21,27,33,35,45,55,63,77,99,105,135,165,189,231,297,315,385,495,693

I think this should work:

var a = [1, 3, 5, 9];
var l = a.length;
var r = [];
for (var i = 0; i < l; ++i) {
  for (var j = i + 1; j < l; ++j) {
    for (var k = j + 1; k < l; ++k) {
      r.push(a[i] * a[j] * a[k]);
    }
  }
}

Edit

Just for my own edification, I figured out a generic solution that uses loops instead of recursion. It's obvious downside is that it's longer thus slower to load or to read. On the other hand (at least on Firefox on my machine) it runs about twice as fast as the recursive version. However, I'd only recommend it if you're finding combinations for large sets, or finding combinations many times on the same page. Anyway, in case anybody's interested, here's what I came up with.

function combos(superset, size) {
  var result = [];
  if (superset.length < size) {return result;}
  var done = false;
  var current_combo, distance_back, new_last_index;
  var indexes = [];
  var indexes_last = size - 1;
  var superset_last = superset.length - 1;

  // initialize indexes to start with leftmost combo
  for (var i = 0; i < size; ++i) {
    indexes[i] = i;
  }

  while (!done) {
    current_combo = [];
    for (i = 0; i < size; ++i) {
      current_combo.push(superset[indexes[i]]);
    }
    result.push(current_combo);
    if (indexes[indexes_last] == superset_last) {
      done = true;
      for (i = indexes_last - 1; i > -1 ; --i) {
        distance_back = indexes_last - i;
        new_last_index = indexes[indexes_last - distance_back] + distance_back + 1;
        if (new_last_index <= superset_last) {
          indexes[indexes_last] = new_last_index;
          done = false;
          break;
        }
      }
      if (!done) {
        ++indexes[indexes_last - distance_back];
        --distance_back;
        for (; distance_back; --distance_back) {
          indexes[indexes_last - distance_back] = indexes[indexes_last - distance_back - 1] + 1;
        }
      }
    }
    else {++indexes[indexes_last]}
  }
  return result;
}

function products(sets) {
  var result = [];
  var len = sets.length;
  var product;
  for (var i = 0; i < len; ++i) {
    product = 1;
    inner_len = sets[i].length;
    for (var j = 0; j < inner_len; ++j) {
      product *= sets[i][j];
    }
    result.push(product);
  }
  return result;
}

console.log(products(combos([1, 3, 5, 7, 9, 11], 3)));

var create3Combi = function(array) {
    var result = [];
    array.map(function(item1, index1) {
        array.map(function(item2, index2) {
            for (var i = index2 + 1; i < array.length; i++) {
                var item3 = array[i];
                if (item1 === item2 || item1 === item3 || item2 === item3 || index2 < index1) {
                    continue;
                }
                result.push([item1, item2, item3]);
            }
        });
    });

    return result;
};

var multiplyCombi = function(array) {
    var multiply = function(a, b){
        return a * b;
    };

    var result = array.map(function(item, index) {
        return item.reduce(multiply);
    });

    return result;
}

var numArr = [1, 3, 5, 9];

//  create unique 3 number combination
var combi = create3Combi(numArr); //[[1,3,5],[1,3,9],[1,5,9],[3,5,9]]

// multiply every combination
var multiplyResult = multiplyCombi(combi); //[15,27,45,135];

A recursive function to do this when you need to select k numbers among n numbers. Have not tested. Find if there is any bug and rectify it :-)

var result = [];

foo(arr, 0, 1, k, n); // initial call

function foo(arr, s, mul, k, n) {
    if (k == 1) {
        result.push(mul);
        return;
    }

    var i;
    for (i=s; i<=n-k; i++) {
        foo(arr, i+1, mul*arr[i], k-1, n-i-1);
    }
}

This is a recursive function.

1. First parameter is array arr.

2. Second parameter is integer s. Each call calculates values for part of the array starting from index s. Recursively I am increasing s and so array for each call is recursively becoming smaller.

3. Third parameter is the value that is being calculated recursively and is being passed in the recursive call. When k becomes 1, it gets added in the result array.

4. k in the size of combination desired. It decreases recursively and when becomes 1, output appended in result array.

5. n is size of array arr. Actually n = arr.length

https://github.com/dankogai/js-combinatorics

Found this library. Tested to be working. Below is from the library document:

var Combinatorics = require('js-combinatorics');
var 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"]

Using node, you can do this pretty easily using a library. First install bit-twiddle using npm:

npm install bit-twiddle

Then you can use it in your code like this:

//Assume n is the size of the set and k is the size of the combination
var nextCombination = require("bit-twiddle").nextCombination
for(var x=(1<<(k+1))-1; x<1<<n; x=nextCombination(x)) {
   console.log(x.toString(2))
}

The variable x is a bit-vector where bit i is set if the ith element is contained in the combination.