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

Answer 2

EDIT: I've made a comparison of the different methods using jsperf here, Phrogz's way is clearly the fastest at twice that of the 3rd here.

---

If I understand correctly, you're asking about counting where each column of digits is a different base. You can do this recursively.

function options(opArr, fullArray){
    var i = 0, j = opArr.length;
    if(j < fullArray.length){ // if opArr doesn't have item from each group, add new group
        while(i < fullArray[j]){ // count up for this group
            newArr = opArr.slice(0); // clone opArr so we don't run into shared reference troubles, not sure if necessary
            newArr[j] = i;
            i++;
            options(newArr, fullArray); // recurse
        }
    }else{ // opArr is now a unique array of your items
        // console.log(opArr);
    }
}
options([], [3, 9, 3, 3]);

Note: this (example) will result in 3 * 9 * 3 * 3 = 243 arrays being made. You can end up eating a lot of memory this way.

---

A different method is converting from an integer to the array, which may save on memory use as you can forget all of the previous calculated arrays

function countUp(arrayOfBases, callback, self){
    var arr = arrayOfBases.reverse(), x = 1, i = arr.length,
        me = (self===undefined?this:self),
        makeArr = function(arr, x, fn, me){
        var a = arr.slice(0), n = [], i = x, j = 0, k = 0;
        while(a.length > 0){
            k = a[0];
            if(k !== 0) j = i % k, i = (i - j) / k;
            else j = 0;
            n.unshift(j);
            a.shift();
        }
        fn.call(me,n);
    };
    while (i-->0) if(arr[i] !== 0) x = x * arr[i];
    i = 0;
    while(i < x){
        makeArr(arr, i, callback, me);
        i++;
    }
}
countUp([3,9,3,3], function(a){console.log(a);});

---

An additional method, similar to the previous, retaining the array produced last time around so there are less computations in loops at the cost of a more at init.

function countUp2(arrayOfBases, callback, self){
    var arr = arrayOfBases.reverse(), x = 1, i = arr.length, last = [],
        me = (self===undefined?this:self),
        addOne = function(arr, n, fn, me){
        var j = n.length, i = j - 1;
        n[i]++;
        while(j = i, i-- > 0 && n[j] >= arr[j]){
            if(arr[j] === 0) n[i] += n[j], n[j] = 0;
            else n[i]++, n[j] -= arr[j];
        }
        return fn.call(me,n.slice(0)), n;
    };
    while (i-->0){
        if(arr[i] !== 0) x = x * arr[i];
        last[i] = 0;
    }
    i = 0;
    last[last.length-1] = -1;
    while(i < x){
        last = addOne(arr, last, callback, me);
        i++;
    }
}
countUp2([3,9,3,3], function(a){console.log(a);});

---

All of these methods will output

[0,0,0,0]
[0,0,0,1]
...
[0,8,1,2]
[0,8,2,0]
...
[2,8,2,1]
[2,8,2,2]

which you can then handle as you choose.

Answer 3

Maybe it's a late answer. But I find a different solution at geeksforgeeks. So anyone can try this.

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

const data = [hats, shirts, pants, shoes];
const keys = ['hats', 'shirts', 'pants', 'shoes'];


function combination(data, keys) {
    const { length: numberOfArrays } = data;
    
    /**
     * Initialize a variable called indices
     * with the length of data array and
     * fill with zeros.
     */
    const indices = Array(numberOfArrays).fill(0);
    const result = [];

    while (true) {
        let obj = {};

        /**
         * Get the values from the inner arrays
         * with help of `indices` and make an object
         */
        for (let i = 0; i < numberOfArrays; i++) {
            obj[keys[i]] = data[i][indices[i]];
        }
        
        // Push the object into the result array
        result.push(obj);

        // Get the last array
        let pick = numberOfArrays - 1;
        
        /**
         * find the rightmost array that has more 
         * elements left after the current element  
         * in that array
         */
        while (pick >= 0 && (indices[pick] + 1 >= data[pick].length)) {
            pick--;
        }

        /**
         * No such array is found so no more  
         * combinations left 
         */
        if (pick < 0) break;

        /**
         * If found move to next element in that array
         */
        indices[pick]++;

        /**
         * for all arrays to the right of this  
         * array current index again points to  
         * first element 
         */
        for (let i = pick + 1; i < numberOfArrays; i++) {
            indices[i] = 0;
        }

    }

    return result;
}

console.log(combination(data, keys));

.as-console-wrapper {min-height: 100%!important; top: 0}