Find all combinations of elements in an array

Question

The problem I am trying to solve is that I want to generate an array which represents all combinations of elements in a source array.

Given an input of 2 items, there are 4 combinations (represented here as binary)

Group 1 | 0 | 1 | 0 | 1
Group 2 | 0 | 0 | 1 | 1
--------------------------
&Result | 0 | 1 | 2 | 3

This can be generalised so the number of combinations is 2^{(number of groups)} (So 3 groups has 8 combinations, 4 has 16 etc).

So the question is; given a javascript array:

var groups = [
{
    name:"group1",
    bit: 1
},
{
    name:"group2",
    bit: 2
},
{
    name:"group3",
    bit: 4
}];

I need to generate an array where the index represents the and'ing of the bit property and the value of the array is arbitrary (further calculation - not relevant) so lets just make it an array of the group names (for the purpose of this question). This result is desirable:

var result = [
    {groups: []}, //0 
    {groups: ["group1"]}, //1
    {groups: ["group2"]},  //2
    {groups: ["group1","group2"]}, //3
    {groups: ["group3"]}, //4
    {groups: ["group1","group3"]}, //5
    {groups: ["group2","group3"]}, //6
    {groups: ["group1","group2","group3"]} //7
]

You can see in the comments there that each index in the array represents the act of and'ing the bit property from the original.

I have prepared a jsfiddle with the input and required output should it be useful in answering the question.

---

This is my current solution, based on mellamokb's answer but re-written in my prefered style. I was hoping there was a more elegant solution as this has a lot of iterations over the array which are unecessary. Any better solutions?

var resultCount = Math.pow(2,groups.length);
var result = [];
for(var i=0;i<resultCount;i++){
    result.push({
        groups: $.map(groups, function(e,idx){ 
           return  ((i & Math.pow(2,idx)) != 0)
               ? e.name
               : null
        })
    });
}

Answer 1

Here is a relatively efficient solution that builds up the arrays by index:

var result = [];
var resultCount = Math.pow(2, groups.length);

for (var i = 0; i < resultCount; i++) {
    result[i] = { groups: [] };
    for (var g = 0; g < groups.length; g++) {
        if (i & groups[g].bit) result[i].groups.push(groups[g].name);
    }
}

Demo: http://jsfiddle.net/7ZsHL/9/

Answer 2

I like what others have done, but in a situation like this, I might choose to be a little mover verbose in my code, as the intent of the algorithm is hard to communicate.

An Update Of Your Fiddle

var groups = [
    {
        name:"group1",
        bit: 1
    },
    {
        name:"group2",
        bit: 2
    },
    {
        name:"group3",
        bit: 4
    }];

function parseIterations(groups){
    var aIterations = [];
    var aBits = [];
    var iGroups = groups.length;
    var iTotalIterations = Math.pow(2, iGroups);
    for (var i = 0; i < iTotalIterations; i++) {
        var oIteration = { groups: [] };
        for (var j = 0; j < iGroups; j++) {
            if (typeof aBits[j] == 'undefined')
                aBits[j] = true;
            // while you could infer the .bit value from j, 
            // i've chosen to use your .bit value here.
            aBits[j] = (i % groups[j].bit == 0) ? !aBits[j] : aBits[j];
            if (aBits[j])
                oIteration.groups.push(groups[j].name);
        }
        aIterations[i] = oIteration;
    }
    return aIterations;
}

var result = parseIterations(groups);

Answer 3

I think you can do it without having to store the bit and what not.

var groups = [
    "group1",
    "group2",
    "group3",
    "group4"
];

var output = [];
for (var i = 0; i < Math.pow(2, groups.length); i++) {
    var arr = [];
    output.push(arr);
    for (var j = 0; j < groups.length; j++) {
        if (i & (Math.pow(2, j))) {
            arr.push(groups[j]);
        } else {
            arr.push(0);
        }
    }
}