Finding number selection possibilities

Question

I have the following example data in javascript:

var variations = [
  {group: 1, id: 1},
  {group: 1, id: 2},
  {group: 1, id: 3},
  {group: 1, id: 4},
  {group: 2, id: 5},
  {group: 2, id: 6},
  {group: 2, id: 7},
  {group: 3, id: 8},
  {group: 3, id: 9}
];

Let us say I already define the selection using the following variables:

var selected_variation_groups = [1,2,3];
var selected_variation_group_ids = [1,2,3,4,5,6,7,8,9];

When I try to find the selection number possibilities from above data, then I would have 24 posibilities:

=> 1, 5, 8
=> 1, 5, 9
=> 1, 6, 8
=> 1, 6, 9
=> 1, 7, 8
=> 1, 7, 9

=> 2, 5, 8
=> 2, 5, 9
=> 2, 6, 8
=> 2, 6, 9
=> 2, 7, 8
=> 2, 7, 9

=> 3, 5, 8
=> 3, 5, 9
=> 3, 6, 8
=> 3, 6, 9
=> 3, 7, 8
=> 3, 7, 9

=> 4, 5, 8
=> 4, 5, 9
=> 4, 6, 8
=> 4, 6, 9
=> 4, 7, 8
=> 4, 7, 9

Is there anyone who can help me to give the algorithm for this, or is there anyone who can help me provide javascript code to create those possibilities?

The groups and ids can be unlimited.

Answer 1

You are computing all permutations of selecting one item from each group.

It's easier to code if you have all the groups arranged as an array, so all group 1's data are in one array, group 2 in another and so on.

This function will add all permutations of the groups to an array, with values separated by commas.

var groups = [
      [1,2,3,4], [5,6,7], [8,9]
];

var result = new Array();
appendPermutation(groups, 0, groups.length, "", result);

alert(result.length);
alert(result);


function appendPermutation(groups, start, end, currentResult, result)
{
   if (start==end)
   {

       result.push(currentResult);
        return;
   }

   var group = groups[start];
   for (var i=0; i<group.length; i++) {
      var value = group[i].toString();
      var nextResult;
      if (currentResult.length==0)
          nextResult = currentResult + value;
      else
          nextResult = currentResult + "," + value;      
      appendPermutation(groups, start+1, end, nextResult, result);
   }
}

Answer 2

mdma already showed how to get the permutation. This code will group the data to a hash collection, as recommended:

var groups = {};
for(var i = 0; i < variations.length; i++){
    var key = variations[i].group;
    var value = variations[i].id;

    if(!groups[key])
        groups[key] = [];
     groups[key].push(value);
}

If you need an array change groups = {}; to groups = [];, but make sure the keys are small numbers, or it might generate a large array (for large number), or add properties (for other strings).

Answer 3

In addition to @mdma's solution, you may find this also useful:

function permutation(options) {
    if(options.length == 1) {
        var permutations = [];
        for(var i = 0; i < options[0].length; i++) {
            permutations.push([options[0][i]]);
        }
        return permutations;
    }
    return addOptionWithPermutation(options[0], permutation(options.slice(1)));
}

function addOptionWithPermutation(option, permutations) {
    var newPermutations = [];
    for(var i = 0; i < option.length; i++) {
        for(var j = 0; j < permutations.length; j++) {
            var newPerm = permutations[j].slice(0); //just to take copy
            newPerm.splice(0, 0, option[i]); //insert in the beginning
            newPermutations.push(newPerm);
        }
    }
    return newPermutations;
}

var permutations = permutation([[1,2,3,4], [5,6,7], [8,9]]);

for(var i = 0; i < permutations.length; i++) {
  alert(permutations[i]);
}