Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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}}
}
Answer: { {{1,3},{1,8}}, {{1,3},{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?

share|improve this question

1 Answer 1

up vote 2 down vote accepted

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.

In your example, you would insert {1,3} in [1] and [3], then you would insert {2,5} in [2] and [5]. Now you go through S2, you see {1,8}, you check indices [1] and [8] (directly) and see there is element in [1] so you output {1,8}{1,3} as an answer. Next you see there is no element in [8] so you proceed next with next element {3,6} by the same way.

Problem with associative field is when you want to use big range of values, but since you only have numbers 1-30, it can help.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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