6

I've currently got a list of tuples (though I control creation of the list and tuples, so they could be altered in type if needed). Each tuple has a start and end integer and a string with an ID for that range's source. What I'm trying to do is identify all of the overlapping ranges within the tuples.

Currently I have

a = [(0, 98, '122:R'), 
     (100, 210, '124:R'),
     (180, 398, '125:R'),
     (200, 298, '123:R')]
highNum = 0
highNumItem = ''
for item in a:
    if item[0] < highNum:
        print(highNumItem + ' overlaps ' + item[2])
        if item[1] > highNum:
            highNum = item[1]
            highNumItem = item[2]

    
# 124:R overlaps 125:R
# 125:R overlaps 123:R

Which outputs enough information that overlaps should be able to be manually review and fixed. But, it misses identifying some sets of overlaps. I can't help thinking there's a relatively obvious solution I'm just missing or not using the right search terms to find examples of. But ideally I'd like the output to actually be

124:R overlaps 125:R & 123:R
125:R overlaps 123:R

But using my comparison method, I can't see a way to catch the rare instance where an overlap spans more than just 2 adjacent ranges. If anyone could point me to a function or comparison method appropriate to this, I'd greatly appreciate.

Also, if it matters, I'm currently stuck with python 2.7, but need to be able to port solution to 3.x when 3rd party applications allow it.

1
  • You have to have two nested for loops, currently you only go through an a one single time. Aug 21, 2020 at 19:47

5 Answers 5

3

Checks the higher number of a pair with the lower number of another pair:

a = [(0, 98, '122:R'), (100, 210, '124:R'), (180, 398, '125:R'), (200, 298, '123:R')]

for i, base_data in enumerate(a):
    for check_data in a[i + 1:]:
        if base_data[1] > check_data[0]:
            print(f"{base_data[2]} overlaps {check_data[2]}")
#prints:
#124:R overlaps 125:R
#124:R overlaps 123:R
#125:R overlaps 123:R

If you want it stored in groups:

from collections import defaultdict

a = [(0, 98, '122:R'), (100, 210, '124:R'), (180, 398, '125:R'), (200, 298, '123:R')]
d = defaultdict(list)

for i, base_data in enumerate(a):
    for check_data in a[i + 1:]:
        if base_data[1] > check_data[0]:
            d[base_data[2]].append(check_data[2])


print(d)
#prints:
#defaultdict(<class 'list'>, {'124:R': ['125:R', '123:R'], '125:R': ['123:R']})
#but can *easily* be iterated over to pretty print:
print("\n".join([f'{key} overlaps {" & ".join(d[key])}' for key in d]))
#prints:
#124:R overlaps 125:R & 123:R
#125:R overlaps 123:R

The dictionary is far better than printing as it actually stores the data instead of just printing it. Printing the data can also be more controlled. Also, using a defaultdict over a dict makes the code more compact.

3

Here is an example using intspan to calculate the overlaps. (Using Python 3.8)

from itertools import combinations
from intspan import intspan

a = [(0, 98, '122:R'), (100, 210, '124:R'), (180, 398, '125:R'), (200, 298, '123:R')]

d = {}
for one, two in combinations(a,2):
    # if the 2 ranges intersect
    if intspan.from_range(*one[0:2]) & intspan.from_range(*two[0:2]):
        d.setdefault(one[2], []).append(two[2])

for key, v in d.items():
    print(key + ',' + ','.join(v))

Prints:

124:R,125:R,123:R
125:R,123:R
2

This should work:

import operator

def get_overlaps(end, remaining):
    output = []
    for r in remaining:
        if r[0] < end:
            # starts before the end
            output.append(r[2])
            continue
        break
    return output

def get_all_overlaps(lst):
    # thanks @Elan-R for this simplification
    for i, (start, end, name) in enumerate(lst):        
        overlaps = get_overlaps(end, lst[i+1:])
        if overlaps:
            print(name, "overlaps", " & ".join(overlaps))


a = [(0, 98, '122:R'), (100, 210, '124:R'), (180, 398, '125:R'), (200, 298, '123:R')]

# sort by start time
a.sort(key=operator.itemgetter(0)) # thanks to @moonGoose
get_all_overlaps(a)

Output:

124:R overlaps 125:R & 123:R
125:R overlaps 123:R

This code iterates over each item in the list, and then checks every subsequent item to see if the start time is less than the end time of the current item. If so, it adds the name to the list of overlaps. If not, it stops checking for the current item, as the start times increase, so there will be no further overlaps.

(Tested for Python 3.6, but should work with any version)

9
  • Instead of for i, item in enumerate(lst): you can usefor i, (start, end, name) in enumerate(lst): which is more pythonic and compact.
    – Elan-R
    Aug 21, 2020 at 20:27
  • You're welcome! Also, putting the break in for r in remaining: assumes the tuples are in order from least to greatest. To be safe, it would be better to take it out (and the continue).
    – Elan-R
    Aug 21, 2020 at 20:34
  • I went for sorting the list to reduce the time complexity, as going over each is a lot more computing time than sorting the list to begin with - O(n^2) vs O(n log n)
    – Ed Ward
    Aug 21, 2020 at 20:56
  • 1
    Two slight tricks: 1) you can define get_overlaps in terms of itertools.takewhile 2) a.sort(key=operator.itemgetter(0))
    – moonGoose
    Aug 21, 2020 at 21:13
  • 1
    @EdWard if overlaps := [o[2] for o in itertools.takewhile(lambda x:x[0] < end, lst[i+1:])]:. If you want even more esoteric, you can use more_itertools.tail, eg. for (_, end, name), *items in (tail(i,lst) for i in range(len(lst)-1, 1, -1)):.
    – moonGoose
    Aug 21, 2020 at 21:34
2

Here it is a solution in python 3.x

    a = [(0, 98, '122:R'), (100, 210, '124:R'), (180, 398, '125:R'), (200, 298, '123:R')]
    
    for i in range(len(a)-1):
        i_low, i_high, i_id = a[i]
        for j in range(i+1, len(a)):
            j_low, j_high, j_id = a[j]
            if i_low < j_low < i_high or j_low < i_low < j_high:
                print(i_id, " overlaps with ", j_id)

In case python 2 didn't support that unpacking system:

    a = [(0, 98, '122:R'), (100, 210, '124:R'), (180, 398, '125:R'), (200, 298, '123:R')]
    
    for i in range(len(a)-1):
        i_low, i_high, i_id = a[i][0], a[i][1], a[i][2]
        for j in range(i+1, len(a)):
            j_low, j_high, j_id =a[j][0], a[j][1], a[j][2]
            if i_low < j_low < i_high or j_low < i_low < j_high:
                print(i_id, " overlaps with ", j_id)
2
  • Instead of saying range(len(a)-1) and then getting the contents of the tuple, you can use for i, (i_low, i_high, i_id) in enumerate(a): and then use the variables the same way.
    – Elan-R
    Aug 21, 2020 at 20:18
  • True, it was a but coding habit that i used to have in the past but i decided to put it here in order to give the code a better readability. Should work as well Aug 24, 2020 at 6:44
2

First, make sure you have sorted your list by interval start values. Then you just need to loop through them and group tuples together as long as their interval start value is lower than the end value of the first group item.

items = [(0, 98, '122:R'), (100, 210, '124:R'), (180, 398, '125:R'), (200, 298, '123:R')]
    
sorted(items, key=lambda x: x[0])

overlaps = []
while items:
  overlap = list(takewhile(lambda item:item[0] < items[0][1],items))
  overlaps.append(overlap)
  items = items[len(overlap):]

Results in overlaps being

[
   [(0, 98, '122:R')],
   [(100, 210, '124:R'), (180, 398, '125:R'), (200, 298, '123:R')]
]

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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