Output each combination of an array of numbers with javascript

Question

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.

Answer 1

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)));

Answer 2

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

Answer 3

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);
    }
}