Efficient way to find pairs which satisfy a certain condition

Question

Let A and B be lists. I was to find all pairs {x,y} for which x is in A, y is in B and some condition Cond[x,y] is true. This is what I've come up with, but its quite cumbersome and I suspect there is a better way

AllPairs[A_, B_, Cond_] := Module[{i, k, C, Cp},
  C = {};
  For[i = 1, i <= Length[A], i++,
  Cp = Select[B, Cond[A[[i]], #] &];
  C = C~Join~Table[{A[[i]], Cp[[k]]}, {k, 1, Length[Cp]}];
 ];
Return[C];
]

For example

In[1]:= AllPairs[{1, 2, 3, 4}, {3, 4, 5}, EvenQ[#1 + #2] &]
Out[1]:= {{1, 3}, {1, 5}, {2, 4}, {3, 3}, {3, 5}, {4, 4}}

My other problem with this code is that it doesn't generalize easily. I would like to have a function which takes in lists A1, A2,...,An and some condition Cond[x___] and outputs all n tuples {x1,x2,...,xn} for which x1 is in A1 ... xn is in An and Cond[x1,x2,...,xn] is true.

And finally, is there a built in function which computes the cartesian product of two or more lists?

Thanks!

Answer 1

If you need to check all pairs (i.e. there is no symmetry to use for reducing the problem), then the simplest is probably Select and Tuples:

allPairs[a_,b_,cond_]:=Select[Tuples@{a,b},cond@@#&];

Which does what I think you want:

a=Range[4]; b=Range[3,5];
allPairs[a,b,EvenQ[#1+#2]&]
Out[37]= {{1,3},{1,5},{2,4},{3,3},{3,5},{4,4}}

As for more tools for generating pairs look up Tuples and Outer:

Tuples[a,2] (* 2-tuples with entries from a *)
Tuples[{a,b}] (* 2-tuples with firt (2nd) entry from a (b) *)
Outer[List,a,b] (* cartesian product *)

Hope this helps.