Ленивое декартово произведение массивов (произвольные вложенные петли)

Ответ 1

Совпадение работает над тем же самым в выходные. Я искал альтернативные варианты реализации моего [].every -элемента, который оказался безупречным в Firefox (но кричит в Chrome - более чем в два раза быстрее, чем в следующем).

Конечный результат http://jsperf.com/lazy-cartesian-product/19. Это похоже на подход Томалака, но есть только один массив аргументов, который мутируется, когда каретки перемещаются, а не генерируются каждый раз.

Я уверен, что его можно было бы улучшить, используя умные математики в других альго. Я не совсем понимаю их, поэтому я оставляю это другим, чтобы попробовать.

EDIT: фактический код, тот же интерфейс, что и Tomalak. Мне нравится этот интерфейс, потому что он может быть break ed в любое время. Он только немного медленнее, чем если петля встроена в саму функцию.

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

Ответ 2

Комбинация рекурсии и итерации выполнит задание.

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

Ответ 3

Здесь мое решение, используя рекурсию. Я не увлекаюсь тем, что он создает пустой массив на первом проходе или использует 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/

Изменить: здесь гораздо более быстрая версия, примерно 2x-10x быстрее, чем указано выше:

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 th для декартова произведения массивов [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 раза медленнее, чем этот ответ.

Ответ 4

Я создал это решение:

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