Lazy Cartesian product of arrays (arbitrary nested loops)

Question

There are other questions about this in other languages, and other non-lazy JavaScript versions, but no lazy JavaScript versions that I have found.

Given an array of an arbitrary number of arbitrary-sized arrays:

var sets = [ [2,3,4,5], ['sweet','ugly'], ['cats','dogs','hogs'] ];

and a callback function:

function holla( n, adj, noun ){
  console.log( [n,adj,noun].join(' ') );
}

what's an elegant way to iterate the entire product space without creating a huge array of all possible combinations first?

lazyProduct( sets, holla );
// 2 sweet cats
// 2 sweet dogs
// 2 sweet hogs
// 2 ugly cats
// 2 ugly dogs
// 2 ugly hogs
// 3 sweet cats
// 3 sweet dogs
// 3 sweet hogs
// 3 ugly cats
// 3 ugly dogs
// 3 ugly hogs
// 4 sweet cats
// 4 sweet dogs
// 4 sweet hogs
// 4 ugly cats
// 4 ugly dogs
// 4 ugly hogs
// 5 sweet cats
// 5 sweet dogs
// 5 sweet hogs
// 5 ugly cats
// 5 ugly dogs
// 5 ugly hogs

---

Note that these combinations are the same as the results you would get if you had nested loops:

var counts     = [2,3,4,5];
var adjectives = ['sweet','ugly'];
var animals    = ['cats','dogs','hogs'];
for (var i=0;i<counts.length;++i){
  for (var j=0;j<adjectives.length;++j){
    for (var k=0;k<animals.length;++k){
      console.log( [ counts[i], adjectives[j], animals[k] ].join(' ') );
    }
  }
}

The benefits of the Cartesian product are:

1. It lets you nest an arbitrary number of loops (perhaps you don't know how many items you'll iterate)
2. It lets you change the order of looping (e.g. loop by adjectives first) without having to edit your code or write out all possible combinations of looping order.

---

Benchmarks

You can see the benchmarks for the answers below here:
http://jsperf.com/lazy-cartesian-product/26

Answer 1

A combination of recursion and iteration will do the job.

function lazyProduct(sets, holla) {
    var setLength = sets.length;
    function helper(array_current, set_index) {
        if (++set_index >= setLength) {
            holla.apply(null, array_current);
        } else {
            var array_next = sets[set_index];
            for (var i=0; i<array_next.length; i++) {
                helper(array_current.concat(array_next[i]), set_index);
            }
        }
    }
    helper([], -1);
}

Demo: http://jsfiddle.net/nV2XU/

var sets = [ [2,3,4,5], ['sweet','ugly'], ['cats','dogs','hogs'] ];
function holla( n, adj, noun ){
  console.log( [n,adj,noun].join(' ') );
}

lazyProduct(sets,holla);

Answer 2

Coincidentally working on the same thing over the weekend. I was looking to find alternative implementations to my [].every-based algo which turned out to have abyssmal performance in Firefox (but screams in Chrome -- more than twice as fast as the next).

The end result is http://jsperf.com/lazy-cartesian-product/19 . It's similar to Tomalak's approach but there is only one arguments array which is mutated as the carets move instead of being generated each time.

I'm sure it could be improved further by using the clever maths in the other algos. I don't quite understand them though, so I leave it to others to try.

EDIT: the actual code, same interface as Tomalak's. I like this interface because it could be breaked anytime. It's only slightly slower than if the loop is inlined in the function itself.

var xp = crossProduct([
  [2,3,4,5],['angry','happy'], 
  ['monkeys','anteaters','manatees']]);
while (xp.next()) xp.do(console.log, console);

function crossProduct(sets) {
  var n = sets.length, carets = [], args = [];

  function init() {
    for (var i = 0; i < n; i++) {
      carets[i] = 0;
      args[i] = sets[i][0];
    }
  }

  function next() {
    if (!args.length) {
      init();
      return true;
    }
    var i = n - 1;
    carets[i]++;
    if (carets[i] < sets[i].length) {
      args[i] = sets[i][carets[i]];
      return true;
    }
    while (carets[i] >= sets[i].length) {
      if (i == 0) {
        return false;
      }
      carets[i] = 0;
      args[i] = sets[i][0];
      carets[--i]++;
    }
    args[i] = sets[i][carets[i]];
    return true;
  }

  return {
    next: next,
    do: function (block, _context) {
      return block.apply(_context, args);
    }
  }
}

Answer 3

Here's my solution, using recursion. I'm not fond of the fact that it creates an empty array on the first pass, or that it uses the if inside the for loop (instead of unrolling the test into two loops for speed, at the expense of DRYness) but at least it's sort of terse:

function lazyProduct(arrays,callback,values){
  if (!values) values=[];
  var head = arrays[0], rest = arrays.slice(1), dive=rest.length>0;
  for (var i=0,len=head.length;i<len;++i){
    var moreValues = values.concat(head[i]);
    if (dive) lazyProduct(rest,callback,moreValues);
    else      callback.apply(this,moreValues);
  }
}

Seen in action: http://jsfiddle.net/RRcHN/

---

Edit: Here's a far faster version, roughly 2x–10x faster than the above:

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);
}

Instead of creating custom arrays for each recursive call it re-uses a single array (p) for all params. It also lets you pass in a context argument for the function application.

---

Edit 2: If you need random access into your Cartesian product, including the ability to perform iteration in reverse, you can use this:

function LazyProduct(sets){
  for (var dm=[],f=1,l,i=sets.length;i--;f*=l){ dm[i]=[f,l=sets[i].length] }
  this.length = f;
  this.item = function(n){
    for (var c=[],i=sets.length;i--;)c[i]=sets[i][(n/dm[i][0]<<0)%dm[i][1]];
    return c;
  };
};

var axes=[[2,3,4],['ugly','sappy'],['cats','dogs']];
var combos = new LazyProduct(axes);

// Iterating in reverse order, for fun and profit
for (var i=combos.length;i--;){
  var combo = combos.item(i);
  console.log.apply(console,combo);
}
//-> 4 "sappy" "dogs"
//-> 4 "sappy" "cats"
//-> 4 "ugly" "dogs"
...
//-> 2 "ugly" "dogs"
//-> 2 "ugly" "cats"

Decoding the above, the nth combination for the Cartesian product of arrays [a,b,...,x,y,z] is:

[
  a[ Math.floor( n / (b.length*c.length*...*y.length*z.length) ) % a.length ],
  b[ Math.floor( n / (c.length*...*x.length*y.length*z.length) ) % b.length ],
  ...
  x[ Math.floor( n / (y.length*z.length) ) % x.length ],
  y[ Math.floor( n / z.length ) % y.length ],
  z[ n % z.length ],
]

You can see a pretty version of the above formula on my website.

The dividends and moduli can be precalculated by iterating the sets in reverse order:

var divmod = [];
for (var f=1,l,i=sets.length;i--;f*=l){ divmod[i]=[f,l=sets[i].length] }

With this, looking up a particular combination is a simple matter of mapping the sets:

// Looking for combination n
var combo = sets.map(function(s,i){
  return s[ Math.floor(n/divmod[i][0]) % divmod[i][1] ];
});

For pure speed and forward iteration, however, see the accepted answer. Using the above technique—even if we precalculate the list of dividends and moduli once—is 2-4x slower than that answer.

Answer 4

I've created this solution:

function LazyCartesianIterator(set) {
  var pos = null, 
      len = set.map(function (s) { return s.length; });

  this.next = function () {
    var s, l=set.length, p, step;
    if (pos == null) {
      pos = set.map(function () { return 0; });
      return true;
    }
    for (s=0; s<l; s++) {
      p = (pos[s] + 1) % len[s];
      step = p > pos[s];
      if (s<l) pos[s] = p;
      if (step) return true;
    }
    pos = null;
    return false;
  };

  this.do = function (callback) { 
    var s=0, l=set.length, args = [];
    for (s=0; s<l; s++) args.push(set[s][pos[s]]);
    return callback.apply(set, args);
  };
}

It's used like this:

var iter = new LazyCartesianIterator(sets);
while (iter.next()) iter.do(callback);

It seems to work well but it is not very thoroughly tested, tell me if you find bugs.

See how it compares: http://jsperf.com/lazy-cartesian-product/8