Effizienter Weg, Paare zu finden, die eine bestimmte Bedingung erfüllen

Question

Lassen Sie A und B Listen werden. Ich sollte alle Paare finden {x,y} für die x ist in A, y ist in B und einige Bedingung Cond[x,y] ist wahr. Dies ist, was ich habe kommen mit, aber es ist ziemlich umständlich, und ich vermute, dass es ein besserer Weg,

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

Zum Beispiel ist

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

Mein anderes Problem mit diesem Code ist, dass es nicht verallgemeinern leicht. Ich möchte eine Funktion haben, die A1, A2,...,An und eine Bedingung Cond[x___] in Listen nimmt und gibt alle n-Tupel {x1,x2,...,xn} für die x1 in A1 ist ... xn ist in An und Cond[x1,x2,...,xn] ist wahr.

Und schließlich, gibt es eine eingebaute Funktion, die die cartesian product von zwei oder mehr Listen berechnet?

Danke!

Answer 1

Wenn Sie alle Paare überprüfen (dh es gibt keine Symmetrie zur Verringerung des Problems zu verwenden), dann ist die einfachste wahrscheinlich Select und Tuples:

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

Welche tut, was ich glaube, Sie wollen:

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

Wie für mehr Werkzeuge für Paare Erzeugung aufblicken Tuples und 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 *) 

Hoffe, das hilft.

Answer 2

Eine alternative Lösung verwendet ReplaceList - es ist etwa 4 Mal langsamer als Janus 'Antwort (und 3 mal langsamer als die ursprüngliche Methode), aber wahrscheinlich mehr Speichereffizienz.

In[1]:= allPairs1[a_,b_,cond_]:=Select[Tuples@{a,b},cond@@#&]; 
In[2]:= allPairs2[a_,b_,cond_]:=ReplaceList[{a,b}, 
            {{___,x_,___},{___,y_,___}}/;cond[x,y]:>{x,y}] 

In[3]:= aa=RandomInteger[{0,10^5},{1000}]; 
In[4]:= bb=RandomInteger[{0,10^5},{1000}]; 

In[5]:= test1=allPairs1[aa,bb,EvenQ[#1+#2]&];//Timing 
Out[5]= {4.99,Null} 

In[6]:= test2=allPairs2[aa,bb,EvenQ[#1+#2]&];//Timing 
Out[6]= {19.12,Null} 

In[7]:= test1==test2 
Out[7]= True 

Answer 3

Für solche Probleme mag ich persönlich Cases verwenden und eine Bedingung anhängen. Ich bin mir nicht sicher über die Effizienz.

lst1 = {1, 2, 3, 4}; 
lst2 = {3, 4, 5}; 
Cases[Tuples[{lst1, lst2}], {x_, y_} /; EvenQ[x + y]] 

Ich finde den Ansatz einfach und vielseitig, zumindest für kleine Listen (vom Typ mit denen ich arbeite!)

Cases[Tuples[{lst1, lst2}], {x_ /; EvenQ[x], y_ /; OddQ[y]}]