javascript - Lazy Cartesian product of arrays (arbitrary nested loops) - Stack Overflow

admin管理员组

文章数量:1193817

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:

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

• javascript

Share Improve this question Follow edited Jun 20, 2020 at 9:12 CommunityBot 111 silver badge asked Feb 23, 2012 at 22:27 PhrogzPhrogz 303k113113 gold badges667667 silver badges756756 bronze badges 3

• Curiousity: Why did you ask this question? – Rob W Commented Feb 23, 2012 at 22:53
• 1 @RobW Because I needed it and couldn't find it. Specifically, my distinct color generator is in the process of getting the ability to use either HSV or Lab, and to iterate those axis in arbitrary order (which makes a difference to the algorithm), and I didn't want to hand-write 12 different sets of 3-nested-for-loops. And now that I've written it, I'm not convinced that my implementation is the most elegant. :) – Phrogz Commented Feb 23, 2012 at 22:59
• 1 Lazy cartesian product, power-set, permutations and combinations are implemented in the js-combinatorics module: github.com/dankogai/js-combinatorics – Erel Segal-Halevi Commented Mar 25, 2014 at 21:27

Add a comment  | 

5 Answers 5

Sorted by: Reset to default 7

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

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

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

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.

As also suggested in the answer that was accepted, the way to go is with an iterator. But I would use a recursive generator function, and one array that is mutated to visit all combinations. This requires less code:

function* cross(sets, result=[]) {
    const n = result.length;
    if (n >= sets.length) return yield result;
    for (const value of sets[n]) {
        result[n] = value;
        yield* cross(sets, result);
    }
    result.pop();
}

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

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

for (const arr of cross(sets)) holla(...arr);

本文标签： javascriptLazy Cartesian product of arrays (arbitrary nested loops)Stack Overflow