CODEWITHSUNDEEP
pythonrangeoverlap
joeqesi
joeqesi

Reputation: 99

Finding range overlap between at least three ranges Python

I have a list of tuples, which I am using to mark the lower and upper bounds of ranges. For example:

[(3,10), (4,11), (2,6), (8,11), (9,11)] # 5 separate ranges.

I want to find the ranges where three or more of the input ranges overlap. For instance the tuples listed above would return:

[(4,6), (8,11)]

I tried the method provided by @WolframH in answer to this post

But I don't know what I can do to:

Upvotes: 1

Views: 2698

Answers (2)

roippi
roippi

Reputation: 25974

You can, of course, solve this by brute-force checking all the combinations if you want. If you need this algorithm to scale, though, you can do it in (pseudo) nlogn. You can technically come up with a degenerate worst-case that's O(n**2), but whatchagonnado.

Basically, you sort the ranges, then for a given range you look to its immediate left to see that the bounds overlap, and if so you then look right to mark overlapping intervals as results. Pseudocode (which is actually almost valid python, look at that):

ranges.sort()

for left_range, current_range, right_range in sliding_window(ranges, 3):
  if left_range.right < current_range.left:
    continue
  while right_range.left < min(left_range.right, current_range.right):
      results.append(overlap(left_range, right_range))
      right_range = right_range.next
  #Before moving on to the next node, extend the current_range's right bound
  #to be the longer of (left_range.right, current_range.right)
  #This makes sense if you think about it.
  current_range.right = max(left_range.right, current_range.right)

merge_overlapping(results)

(you also need to merge some possibly-overlapping ranges at the end, this is another nlogn operation - though n will usually be much smaller there. I won't discuss the code for that, but it's similar in approach to the above, involving a sort-then-merge. See here for an example.)

Upvotes: 0

dnalow
dnalow

Reputation: 984

You first have to find all combinations of ranges. Then you can transform them to sets and calculate the intersection:

import itertools


limits = [(3,10), (4,11), (2,6), (8,11), (9,11)]
ranges = [range(*lim) for lim in  limits]

results = []
for comb in itertools.combinations(ranges,3):
    intersection = set(comb[0]).intersection(comb[1])
    intersection = intersection.intersection(comb[2])
    if intersection and intersection not in results and\
       not any(map(intersection.issubset, results)):
        results = filter(lambda res: not intersection.issuperset(res),results)
        results.append(intersection)


result_limits =  [(res[0], res[-1]+1) for res in map(list,results)]

It should give you all 3-wise intersections

Upvotes: 1

Related Questions