4
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ Your approach with Outer will work if you specify Nothing as the third argument of If $\endgroup$ – Simon Woods Feb 3 '16 at 21:24
  • 2
    $\begingroup$ Amazing, I did not know about Nothing! (And I love this paradoxical admission) $\endgroup$ – Ziofil Feb 3 '16 at 21:26
  • 2
    $\begingroup$ In the past, it was called the "vanishing function" (by Mr. Wizard) and was implemented like this: ## &[]. I still use this because I still have V10.0. $\endgroup$ – march Feb 3 '16 at 22:14
  • 5
    $\begingroup$ @march ##&[] evaluates to Sequence[] which is broader in scope than Nothing. But, the biggest difference, AFAIK, is that they have different reactions to Hold. Sequence requires the SequenceHold attribute to hold it, Nothing is fine with HoldAll and its kin, e.g. If[a, first, Nothing] vs. If[a, first, Sequence[]]. Hence, the use of the function. $\endgroup$ – rcollyer Feb 4 '16 at 4:52
  • 2
    $\begingroup$ @march just note that Nothing only works in List and Association, so in a lot of cases where ##&[] is needed, Nothing won't work. $\endgroup$ – rcollyer Feb 4 '16 at 15:55
1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ I think this is neater way Fold[Select[(Flatten /@ Tuples[{##}]), criterion] &, lists]. A little faster than your version $\endgroup$ – matheorem Aug 29 '16 at 4:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.