数组的懒惰笛卡尔积(任意嵌套循环)

Question

在 其他 语言和其他非懒惰的 JavaScript版本中还有其他问题,但我找不到懒惰的JavaScript版本.

给定一个任意数量的任意大小数组的数组:

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

---

请注意,这些组合与嵌套循环时获得的结果相同:

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

笛卡尔积的好处是:

1. 它允许你嵌套任意数量的循环(也许你不知道你会迭代多少项)
2. 它允许您更改循环的顺序(例如,首先通过形容词循环),而无需编辑代码或写出循环顺序的所有可能组合.

---

基准

您可以在此处查看以下答案的基准:http:
//jsperf.com/lazy-cartesian-product/26

Answer 1

递归和迭代的组合将完成这项工作.

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

演示: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

这是我的解决方案,使用递归.我不喜欢它在第一次传递时创建一个空数组的事实,或者它使用循环if内部for(而不是将测试展开为两个循环以获得速度,而牺牲了DRYness)但至少它是排序的简洁:

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

见过:http://jsfiddle.net/RRcHN/

编辑:这是一个更快的版本,大约比上面快2倍-10倍:

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

它不是为每个递归调用创建自定义数组,而是p为所有参数重用一个数组().它还允许您传递函数应用程序的上下文参数.

编辑2:如果您需要随机访问笛卡尔积,包括反向执行迭代的功能,您可以使用:

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"

解码上面,阵列的笛卡尔积的第n个组合[a,b,...,x,y,z]是:

[
  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 ],
]

您可以在我的网站上看到上述公式的漂亮版本.

通过以相反的顺序迭代集合,可以预先计算红利和模数:

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

有了这个,查找特定组合就是映射集合的简单问题:

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

但是,对于纯粹的速度和前向迭代,请参阅接受的答案.使用上述技术 - 即使我们预先计算一次股息和模数列表 - 比该答案慢2-4倍.

Answer 3

我创建了这个解决方案:

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

它的使用方式如下:

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

它似乎运行良好,但它没有经过彻底的测试,告诉我你是否发现了错误.

看看它如何比较:http://jsperf.com/lazy-cartesian-product/8

Answer 4

巧合的是周末同样的事情.我正在寻找[].every基于我的基础算法的替代实现,结果证明它在Firefox中具有深度表现(但在Chrome中发出尖叫声 - 比下一代快两倍).

最终结果是http://jsperf.com/lazy-cartesian-product/19.它类似于Tomalak的方法,但是只有一个参数数组随着插入符移动而不是每次生成而变异.

我相信通过在其他算法中使用聪明的数学可以进一步改进它.我不太了解他们,所以我把它留给别人试试.

编辑:实际代码,与Tomalak相同的界面.我喜欢这个界面,因为它可以随时break编辑.它仅比在函数本身内联循环时稍微慢一些.

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