# In A Cross Product Of Pairs, Find Elements Where Both Pairs Contain The Same Number

We have a set S1 consisting of pairs of numbers between 1 and 30, eg:

{ {1,3}, {2,5}, {1,8}, ...}


This set may be all (30 choose 2) of the possibilities, or any subset of them (these are sets, not tuples, so order does not matter).

We have another set S2 generated the same way, but not necessarily identical to S1.

Now take the cross product of S1 and S2. We wish to find all elements of this cross product where the same number exists in both pairs. An example should clarify:

S1 = { {1,3}, {2,5} }
S2 = { {1,8}, {3,6} }
S1 cross S2 = {
{{1,3},{1,8}},
{{1,3},{3,6}},
{{2,5},{1,8}},
{{2,5},{3,6}}
}

since both elements contain a 1 in the first case,
and both elements contain 3 in the second case


Of course, the naive algorithm here is to compute the entire cross product, then loop through each element and do 4 comparisons to see if there is any overlap.

My question is this: Is it possible to do much better than that? Are there any clever tricks to be used here that would allow us to find this set of "overlapping" cross product elements in a computationally fast way?

-

What if you would use associative field? You will have field with indices $[1,\dots,30]$ You can insert pair elements of S1, you insert each pair element twice, for both numbers. For example {1,3} you insert in indices [1] and [3]. Now you go through S2 and check for each pair element, if there is something inserted in field.