Эффективный способ найти пары, которые удовлетворяют определенному условию

Question

Пусть A и B будут списками.Я должен был найти все пары {x,y}, для которых x в A, y в B и некоторое условие Cond[x,y] верно.Это то, что я придумал, но это довольно громоздко, и я подозреваю, что есть лучший способ

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

Например

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

Моя другая проблема с этим кодом заключается в том, чтоэто не обобщает легко.Я хотел бы иметь функцию, которая принимает в списки A1, A2,...,An и некоторые условия Cond[x___] и выводит все n кортежей {x1,x2,...,xn}, для которых x1 находится в A1 ... xn находится в An иCond[x1,x2,...,xn] верно.

И, наконец, есть ли встроенная функция, которая вычисляет декартово произведение из двух или более списков?

Спасибо!

Answer 1

Если вам нужно проверить все пары (т. Е. Не нужно использовать симметрию для уменьшения проблемы), то, вероятно, самое простое - Select и Tuples:

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

Что делает то, что ядумаю, что вы хотите:

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

Что касается других инструментов для генерации пар, посмотрите Tuples и 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 *)

Надеюсь, это поможет.

Answer 2

Для подобных задач лично мне нравится использовать Случаи и ставить условие.Я не уверен насчет эффективности.

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

Я считаю этот подход простым и универсальным, по крайней мере для небольших списков (типа, с которым я работаю!)

Answer 3

В альтернативном решении используется ReplaceList - это примерно в 4 раза медленнее, чем ответ Януса (и в 3 раза медленнее, чем оригинальный метод), но, вероятно, более эффективно использует память.

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