Algorithm to get all possible sets

Question

Input:

[ [a1,b1,c1], [a2,b2,c2,d,2], [a3,b3], ...]

Output:

[ [a1,a2,a3], [a1,a2,b3], [a1,b2,a3], [a1,b2,b3], [a1,c2,a3], [a1,c2,b3], ... ]

So I need combination of all possible sets (order does not matter). Each output set nth member is a member of nth input set. I need efficient algorithm, preferably in javascript.

edit

Well I am trying to solve this.

var input = [ [a,b,c], [a1,b1,c1], [a2,b2] ];

var combinationsNum = _.reduce(input,function(num,set){ return num*set.length; }, 1);
var output = new Array(combinationsNum);
for(var i = 0; i < output.length; ++i) output[i] = [];

for(var s = 0; s < input.length; ++s) {
    var set = input[s];
    for(var m = 0; m < set.length; ++m) {
        var memeber = set[m];
        // now I need to calculate to which output arrays I have to push this member
    }
}

// result should be
// a a1 a2
// a b1 b2
// a c1 a2
// a a1 b2
// a b1 a2
// a c1 b2
// b a1 a2
// b b1 b2
// b c1 a2
// b a1 b2
// b b1 a2
// b c1 b2
// c a1 a2
// c b1 b2
// c c1 a2
// c a1 b2
// c b1 a2
// c c1 b2

As you can see on each set I have to push each of its members to each output array with some interval and times... I have problem of calculating this...

The fastest method I found in this duplicate question is:

function(arg) {
    var r = [], max = arg.length-1;
    function helper(arr, i) {
        for (var j=0, l=arg[i].length; j<l; j++) {
            var a = arr.slice(0); // clone arr
            a.push(arg[i][j])
            if (i==max) {
                r.push(a);
            } else
                helper(a, i+1);
        }
    }
    helper([], 0);
    return r;
};

Please show your attempt. – Abhishek Bansal Nov 18 '13 at 08:26 — Abhishek Bansal, Nov 18 '13 at 08:26

score 1 · Answer 1 · answered Nov 18 '13 at 09:19

One possible way to accomplish this is using recursion. I am not familiar with JavaScript, following is a C++ version. You can adapt it accordingly.

#include <iostream>
#include <vector>

using namespace std;

vector< vector<int> > input;

void recurCombination( vector<int>& outputSoFar ) {

  // base case: If number of entries in our output = size of input array, then print it.
  if ( outputSoFar.size() == input.size() ) {
    // print outputSoFar
    return;
  }

  // else take next subarray in the input array.
  int sizeSofar = outputSoFar.size();    

  // for each element in that subarray, choose an element and recur further.
  for ( int i = 0; i < input[sizeSoFar].size(); i++ ) {
    vector<int> newSoFar( outputSoFar );
    newSoFar.push_back( input[sizeSoFar][i] );
    recurCombination( newSoFar )

  }

}

int main() {

  // read input vector
  vector<int> emptySoFar;
  recurCombination( emptySoFar );

  return 0;
}

score 1 · Answer 2 · answered Nov 18 '13 at 09:28

Since the number of elements you have in the output is length1*length2*...lengthN, an algorithm that simply iterates over each array and build the output is the most efficient you can get.

function buildAll(arr){  
  var i;
  // count the total number of arrays in the output
  var count = 1;
  for (i=0; i<arr.length; i++) {
    count *= arr[i].length; // fails if empty arrays are in input, make sure you extract those
  }

  // prepare the output arrays
  var output = [];
  for (i=0; i<count; i++) {
    output.push([]);
  }

  // fill the arrays
  var total = count;
  for (i=0; i<arr.length; i++) {
    count /= arr[i].length;
    for (var k=0; k<total; k++) {
      output[k].push(arr[i][Math.floor((k/count)%arr[i].length)]);      
    }    
  }

  return output;
}


// usage
var input = [ ['a1','b1','c1'], ['a2','b2','c2','d2'], ['a3','b3']];
var output = buildAll(input);
console.log(output);

DEMO: http://jsbin.com/UfAnIMus/1/edit

tom · Answer 3 · 2013-11-19T11:19:16.873

function concat(a, b)
{
    return a.concat(b);
}

function combinations(a)
{
    return a.length == 0 ? [[]] : a[0].map(function(x) {
        return combinations(a.slice(1)).map(concat.bind(null, [x]));
    }).reduce(concat, []);
}

Couldn't resist ;)

Edit:

Here is a fixed version of the original code.

var lengths = input.map(function(a) { return a.length; });
function product(arr) { return arr.reduce(function(a, b) { return a * b; }, 1); }

var numCombinations = product(lengths);
var output = new Array(numCombinations);

for(var i = 0; i < output.length; ++i) output[i] = [];

for(var s = 0; s < input.length; ++s) {
    var set = input[s];
    var runLength = product(lengths.slice(s + 1));
    var j = 0;
    while (j < numCombinations) {
        for (var m = 0; m < set.length; ++m) {
            for (var i = 0; i < runLength; i++) {
                output[j][s] = set[m];
                j++;
            }
        }
    }
}

Explanation:

The pattern of any given array position is relatively simple. As an example, consider the possible combinations for the sets [ {a1, b1, c1}, {a2, b2, c2}, {a3, b3} ]:

[a1, a2, a3]
[a1, a2, b3]
[a1, b2, a3]
[a1, b2, b3]
[a1, c2, a3]
[a1, c2, b3]
[b1, a2, a3]
[b1, a2, b3]
[b1, b2, a3]
...

The elements in the second column cycle through the values {a2, b2, c2} with each element repeated twice. In general, the number of repetitions is equal to the number of combinations of the remaining sets (which is the product of their sizes). The only remaining set after the second column is {a3, b3} which has size 2, so each element appears twice. With the first column, the remaining sets are {a2, b2, c2} and {a3, b3} so the product of their sizes is 3 × 2 = 6, which is why a1 appears 6 times.

Algorithm to get all possible sets

3 Answers3