Finding overlapping numbers in a tuple in python

Question

I'm working on an NLP project and I have a list with character spans in some text. This list could look like the following:

 [(1,4),(1,7),(4,9),(8,15)]

So my task is to return all non-overlapping pairs. If two or more number pairs are overlapping, then the pair with the longest span should be returned. In my example, I want to return [(1,7),(8,15)] . How can I do this?

EDIT

I don't want to merge my intervals like in Merge overlap here. But i wan't to return all pairs/intervals/tuples except if the values in some tuples overlaps. e.g. (1,4) and (1,7) overlaps, (4,9) overlaps with (1,4) and (1,7) . If there is some overlap i want to return the tuple with the largest span e.g. (1,7) = span 7, (1,4) = span 4, (4,9) = span 5. That means that it should return (1,7) and (8,15) as well since (8,15) are not overlapping (1,7)

What did you try so far? And what exactly do you mean by 'overlapping'? — trotta, Feb 21 '19 at 13:12
@ThierryLathuille tried to edit my question. As far as i can see it is not the same. — XRaycat, Feb 21 '19 at 13:28
@trotta To be honest, i haven't tried much because i don't know where to start. — XRaycat, Feb 21 '19 at 13:30

score 1 · Accepted Answer · answered Feb 21 '19 at 14:59

Haven't thought about it too much, but the following approach should do the trick:

spans = [(1,4),(1,7),(4,9),(8,15)]

del_in = []

for x in spans:
  if spans.index(x) in del_in: continue
  for y in spans:
    if spans.index(y) in del_in: continue
    if x == y: continue
    if len(set(list(range(x[0],x[1]+1))) & set(list(range(y[0],y[1]+1)))) > 0:
      if len(list(range(x[0],x[1]+1))) > len(list(range(y[0],y[1]+1))):
        del_in.append(spans.index(y))
        spans.pop(spans.index(y))
      elif len(list(range(y[0],y[1]+1))) > len(list(range(x[0],x[1]+1))):
        del_in.append(spans.index(x))
        spans.pop(spans.index(x))

print(spans)

Would output:

[(1, 7), (8, 15)]

Short explanation: We start to iterate through the list of spans (iteration x). For every tuple, we iterate again through the list (iteration y), neglecting the tuple from x (if x == y: continue). We then transform every tuple into a list (e.g. (1,4) to [1, 2, 3, 4]) with list(range()) and compare the lists (as possible with set()) to see if they have any element in common. If the length of the returned object is bigger than 0, we compare the length of the two lists to see which one we keep (the one with the bigger span). Subsequently, we delete the item with the smaller span from our list (with .pop()). Since our iterations x and y still go through our initial list, we need to implement a mechanism to prevent the script from comparing items with already deleted entries. Hence, we work with an additional list containing die indexes of entries we already deleted (and leave them out in the two for loops).

There might be a better way to do this, but this definitely works for your example.

Thank you, i would never had figured it out by my self :). I tested it today and i can see that if i input [(4, 7), (5, 7), (6, 7), (10, 11)] it outputs [(4, 7), (6, 7), (10, 11)] instead of [(4, 7), (10, 11)]. So I need to run the code twice to end out with [(4, 7), (10, 11)]. I only need to run the code once on a large text file, so for me, it's fine to run it multiple times. I am just telling if If others want to use the code. — XRaycat, Feb 22 '19 at 12:37

Finding overlapping numbers in a tuple in python

1 Answers1