Return to Revisions

The implementation of lazy tuples here pretty much contains the solution to the lazy Outer problem. I will take the relevant parts from that code.

The following code constructs a function take, which would, given the start and end positions in the flat list of the resulting combinations, extract the elements:

ClearAll[next]; next[{left_, _}, dim_] := {left - dim*(# - 1), #} &[IntegerPart[(left - 1)/dim] + 1]; ClearAll[multiDims]; multiDims[dims_] := Rest @ Reverse @ FoldList[Times, 1, Reverse @ dims]; ClearAll[multiIndex]; multiIndex[pos_, dims : {__Integer}] := Rest@FoldList[next, {pos, 0}, multiDims@dims][[All, 2]] ClearAll[take]; take[lists : {__List}, {start_, end_}] := With[{rend = Min[end, Times @@ Map[Length, lists]]}, Transpose @ MapThread[ Part, {lists, multiIndex[Range[start, rend], Length /@ lists]} ] ]; 

For example,

take[{{1, 2, 3}, {4, 5, 6}}, {3, 7}] == Tuples[{{1, 2, 3}, {4, 5, 6}}][[3 ;; 7]] (* True *) 

The difference is of course, that take only computes those elements that have been requested, so can be used as a basis for a lazy implementation.

Here is then an implementation of an iterator, that would return consecutive combinations in chunks of specified length:

ClearAll[makeTupleIterator]; makeTupleIterator[lists:{__List}, chunkSize_Integer?Positive]:= With[{len=Times @@ Length /@ lists}, Module[{ctr = 0}, If[ctr >= len, {}, (* else *) With[{taken = take[lists,{ctr+1, Min[ctr+chunkSize,len]}]}, ctr += Length[taken]; taken ] ]& ] ]; 

Here is an example: we construct an iterator with the chunk size of 10 elements:

iter = makeTupleIterator[{{"11", "12", "13"}, {"21", "22"}, {"31"}, {"41", "42"}}, 10]; 

Now we use it:

iter[] (* { {"11","21","31","41"}, {"11","21","31","42"}, {"11","22","31","41"}, {"11","22","31","42"}, {"12","21","31","41"}, {"12","21","31","42"}, {"12","22","31","41"}, {"12","22","31","42"}, {"13","21","31","41"}, {"13","21","31","42"} } *) iter[] (* {{"13", "22", "31", "41"}, {"13", "22", "31", "42"}} *) iter[] (* {} *) 

When we get an empty list, this tells us that the iterator has been exhausted.

This basically implements lazy tuples, and therefore also lazy Outer, more or less. You gain efficiency by picking large enough chunks, since chunk extraction (take function) is pretty fast, compared to the top-level iteration that would be needed to extract element by element.