One solution involves iterating the set, while iterating another set. In python, however, I like to create dictionary keys to avoid creating a second loop iteration.
If keying all elements of a set (and there are one and only one such element of such set...not a list in otherwords), then you could check for set intersection creating an iteration on the first set and checking inclusion on the second set.
code:
for element in set1:
if element in set2:
found intersection
Another method in more specialized cases:
If you have an ordered and quasi continuous set of element...by continuous or discretely continuous, by discretely continuous this means in python for an ordered pair (a,b), all elements of range(a, b+1) exist
in such set, or read another way, for an ordered pair (a, b), elements a, a+1, ..., b-1, b exist in such set and no element c exists such that a < c < b where c is not in the set of range(a,b). In this case, one can compare address range by the ordered pair (a,b) and another set (e, f) where if a > e and a < f or b > e and b < f or a < e and b > f, similarly one can compare the elements e and f with a and b. This should at least determine if intersection on a range of elements exists without having to iterate each and every element of two corresponding sets.
Potentially if intersections do exist, this could be faster or slower then iterating all elements of a set if depending. Potentially in this case, you could find within two calculation steps, or as many as the number of conditionals listed above through the full series of checks as compared to a total step wise calculation of the length of set1 * 2 adding the conditional in the previous case.
I would mention method two is more advantageous when the smallest of two sets is larger then the step wise algorithm itself. In this case probably exceeding more then say 6 elements.
Considering now an additional problem and solution using the second method above. If you have a family of sets to compare in this set intersection problem where each set are ordered and continuous, then you could use keyed addressing range for all such sets, and eliminate through address determination your existing set in so far as its placement relative the others, possible sets that could intersect before ever having checked for set intersection. This would be useful in the case of high volume intersection searches.
Example of this in the one dimensional case on the set of positive integers J are:
addresses given as follow address_ranges = {'1': range(0,10), '2': range(10,20),...,range(n-10, n)} where n is some integer in the set J.
If you has an ordered set range(3,15), then addressing blocks in the keyed case above are '1','2' and any set in a family, keyed as '1' and '2' should be checked for intersection, while those outside such range are ignored.
If using block addressing ranges, keep
in mind interior block addresses that coincide with other blocks need
not be searched for intersection element by element here since all
such interior points if a address matche coincides with another
interior block at the same address. Why? Since if in constructing
from a range several blocks where there exists block addresses a and
c such that for block address b, a < b < c, implies b fills
ordered and continuous points at address b.
example, consider as previously
mentioned in the one dimensional case range(10, 45), then the
following block addresses suffices, (1, 2, 3, 4) where block
addresses: 2 and 3 are interior and elements at such block address
exist in such such subset block range. While for endpoint block
addresses 1 and 4 the same claim could not be made, at least we can
say this for are range(10,45) whose block 4 range subset consists of
elements (40, 41, 42, 43, 44, 45).
No comments:
Post a Comment