Find all combinations of options in a loop

Question

I'm looking for the best way to loop through a bunch of options to make sure that I hit all available options.

I've created a feature that allows a client to build images that are basically other images layered on top of each other. These other images are split up into different groups. They have links on the side of the image that they can click to scroll through all the different images to view them.

Now I'm making an automated process that is going to run the function that changes the image when a user clicks one of the links. I need to make sure that every possible combo of the different images is hit during this process.

Say there are 3 different hats, 4 different shirts, 5 different pairs of pants and 6 different pairs of shoes. I can represent this as an array with the number of options for each group. The current array is [3, 4, 5, 6].

What is the best way to loop through this array to make sure that all possible options will be shown?

Answer 1

You want the Cartesian Product of all your arrays.

I have a page discussing this, including implementations in JavaScript, on my site:
http://phrogz.net/lazy-cartesian-product

For example, to iterate through them all quickly in "forward" order, you can use:

hats   = ['fez','fedora']
shirts = ['t-shirt','long']
pants  = ['shorts','jeans']
shoes  = ['sneaker','loafer']

lazyProduct( [hats,shirts,pants,shoes], function(hat,shirt,pant,shoe){
  // Your function is yielded unique combinations of values from the arrays
  console.log(hat,shirt,pant,shoe);
});

function lazyProduct(sets,f,context){
  if (!context) context=this;
  var p=[],max=sets.length-1,lens=[];
  for (var i=sets.length;i--;) lens[i]=sets[i].length;
  function dive(d){
    var a=sets[d], len=lens[d];
    if (d==max) for (var i=0;i<len;++i) p[d]=a[i], f.apply(context,p);
    else        for (var i=0;i<len;++i) p[d]=a[i], dive(d+1);
    p.pop();
  }
  dive(0);
}

The output:

fez t-shirt shorts sneaker
fez t-shirt shorts loafer
fez t-shirt jeans sneaker
fez t-shirt jeans loafer
fez long shorts sneaker
fez long shorts loafer
fez long jeans sneaker
fez long jeans loafer
fedora t-shirt shorts sneaker
fedora t-shirt shorts loafer
fedora t-shirt jeans sneaker
fedora t-shirt jeans loafer
fedora long shorts sneaker
fedora long shorts loafer
fedora long jeans sneaker
fedora long jeans loafer
fez t-shirt shorts sneaker
fez t-shirt shorts loafer

This is identical to the results of:

hats.forEach(function(hat){
  shirts.forEach(function(shirt){
    pants.forEach(function(pant){
      shoes.forEach(function(shoe){
        console.log(hat,shirt,pant,shoe);
      });
    });
  });
});

or (for older browsers):

for (var h=0;h<hats.length;h++){
  var hat = hats[h];
  for (var s=0;s<shirts.length;s++){
    var shirt = shirts[s];
    for (var p=0;p<pants.length;p++){
      var pant = pants[p];
      for (var e=0;e<shoes.length;e++){
        var shoe = shoes[e];
        console.log(hat,shirt,pant,shoe);        
      }
    }
  }
}

…but it supports an arbitrary number of arrays defined at runtime. (And if you're using the first "lazy" implementation from my site, you can pick out items at random, iterate in reverse, or easily stop iteration at any point.)