Efficiently generating tuples with Outer

Question

I'm trying to efficiently generate tuples of lists of objects that satisfy a given criterion. The similar questions that I have found on this website end up finding a specific workaround for the given problem.

An inefficient way of doing what I want is

Select[Tuples[lists] , criterion]

which is inefficient because MMA first needs to generate and store all the tuples. I'm thinking of using Outer, but I'm not sure how. I've tried something that in my head should work but in reality it does not:

Outer[If[#1 === a || #2 === 2, {##}] &, {a, b, c}, Range[2]]

(* {{{a, 1}, {a, 2}}, {Null, {b, 2}}, {Null, {c, 2}}} *)

What it wants to do is to leave the tuple in place if it satisfies the criterion or else remove it: I would like the output to be (in this case)

(* {{{a, 1}, {a, 2}}, {{b, 2}}, {{c, 2}}} *)

How do I do it?

EDIT: Thanks to the comments I have put to together this solution (which gives the same output of Select[Tuples[{list1,list2,...}], criterion@@##]):

f = Flatten[Outer[If[criterion@Flatten[{##}], Flatten[{##}], Nothing]&, ##, 1], 1] &

Fold[f, {list1, list2,list3,...}]

Which also allows one to apply the criterion on all the elements of a tuple.

Answer 1

Solution

Here is a way of efficiently generating tuples of objects that satisfy a given criterion (criterion, which takes a list of objects and returns True or False). We consider the general case of creating tuples from several lists of objects.

This works best if the criterion can be applied before reaching the desired tuple length. (e.g. if I want to make tuples that contain only even numbers, I can discard a partial tuple as soon as it contains an odd number).

Start by defining a filtering function that deletes lists of objects that fail to satisfy the criterion.

filter = Module[{tuple = Flatten[{##}]}, If[criterion@tuple, tuple, Nothing]] &;

Then apply it to pairs of lists using Outer with the third argument set to 1 (so that Outer stops at the first level):

generator = Flatten[Outer[filter, ##, 1], 1] &;

Finally, fold the generator function on all the lists of objects, one by one:

Fold[generator,{list1,list2,...}]

This makes sure that we don't carry over to the next call of Outer lists that already fail to satisfy the criterion.

Performance

We will generate random matrices (e.g. 8 by 4) of numbers between 0 and 10 and we create tuples of even numbers out of the rows.

testList := RandomInteger[10, {8, 4}]
criterion = VectorQ[#, EvenQ] &;

Then we have

Mean@ParallelTable[First@AbsoluteTiming[tuples@testList;], {1000}];
(* 0.027 *)

On my modest machine I get an average of 0.03 seconds per tuple. Let's try a different way:

Mean@ParallelTable[First@AbsoluteTiming[Select[Tuples@testList, criterion];], {1000}];
(* 0.28 *)

Done inefficiently it takes about 10 times longer, but these numbers vary wildly for different problems.