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.

Galata

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.) – Miaow

@Galata Note: You have strings in your array, not numbers. – Dachy

@Sime Vidas - That was a mistake, they should be numbers not strings – Galata

@Galata Are the numbers in the array distinct? – Dachy

@Sime Vidas - Not always, there could be duplicate numbers within the array – Galata

@Galata Does the length of the array vary? – Dachy

@Sime Vidas - Yes, the array could contain anything between 2 and 10 numbers – Galata

You aren't in the same class as stackoverflow.com/users/181557/ebae are you? #4058212 (He got better answers) – Octavus

Answer 1

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

Miaow

Answer 2

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

Histo

If I wanted to get all 2 number combinations or 5 number combinations (if I had a longer array), is there a solution where I can specify that value as a variable (I'm talking about specifying the length of the combinations). – Galata

@Galata if you want to vary that, then my solution's too specific. See Marcelo's more generic solution. – Histo

Your solution actually answers my original question but Marcelo's is exactly what I was after. Thanks for your input. – Galata

Answer 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];

Olmos

Answer 4

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

Nefarious

@ Niraj - Can you explain what each of the parameters are please? – Galata

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 – Nefarious

That's what I thought but I'm still making a mistake somewhere. I'm calling the function like this: var arr = [2, 1, 4, 1, 6]; foo(arr, 0, 1, 4, 5); and outputting it like this: document.write(result); What am I doing wrong? – Galata

Answer 5

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"]

Phytopathology

Answer 6

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.

Rafa