CODEWITHSUNDEEP
pythonlistsearchtuplesoverlap
ponycat
ponycat

Reputation: 189

How to find tuples that overlap a given range tuple

Say I have a list full of tuples denoting a "from" and a "to" time:

tuples = [ (0, 5), (5, 10), (10, 15), (15,20) ]

And I want to be able to retrieve a list of tuple that overlap with a given tuple:

searchTuple = (3,11)
result = findOverlap(tuples, searchTuple)

This code should return the following list:

[ (0, 5), (5, 10), (10, 15) ]

While a searchTuple of (16, 22) should only return the last tuple (15,20)

What is the most efficient way to code this retrieval? I tried various things but I am having trouble getting the algorithm to work properly. I figured the following different "overlaps" that I am interested in catching:

a) tuple_min < find_min AND tuple_max > find_max

search tuple -> |         | 
            |----------------| the search tuple is entirely contained

b) tuple_min > find_min AND tuple_max > find_max

         |         |
            |----------------| the left part of the tuple overlaps

c) tuple_min < find_min AND tuple_max < find_max

              |         |
    |----------------| the right part of the tuple overlaps

However, the results I got after implementing this ended up giving me wrong results... Where is my thinking wrong?

Upvotes: 4

Views: 4386

Answers (6)

Moh Zah
Moh Zah

Reputation: 292

This is the dumbest code you can write:

def findOverlap(tuples, searchTuple):
    result = []
    for p in tuples:
        if  (p[0] <= searchTuple[0] and searchTuple[0] <p[1]) or \
            (p[0] < searchTuple[1] and p[1] >searchTuple[1]) or \
            (p[0] < searchTuple[0] and p[1] searchTuple[1]):
            result.append(p)
        if (p[0] > searchTuple[1]):
            break

I hope I have not mistaken the indexes! if you sort tuples you can improve code performance by doing a smarter search. I came across similar problem years ago when I was trying to learn algorithms. so I guess it is a popular type of question and you can find efficient codes by googling

Upvotes: 2

nicolas.leblanc
nicolas.leblanc

Reputation: 630

This is my solution:

tuples = [ (0, 5), (5, 10), (10, 15), (15,20) ]
searchTuple = (3,11)
result = [tInnerRange for tInnerRange in tuples if searchTuple[0] >= tInnerRange[0] and searchTuple[0] < tInnerRange[1] or searchTuple[1] > tInnerRange[0] and searchTuple[1] <= tInnerRange[1] or searchTuple[0] <= tInnerRange[0] and searchTuple[1] >= tInnerRange[1]]

================================================================================

Here are some sample output for various values of 'searchTuple':

# In this case, 'searchTuple' is overlaping 2 ranges, and bounds don't coincide
tuples = [ (0, 5), (5, 10), (10, 15), (15,20) ]
searchTuple = (8,11)
result = [tInnerRange for tInnerRange in tuples if searchTuple[0] >= tInnerRange[0] and searchTuple[0] < tInnerRange[1] or searchTuple[1] > tInnerRange[0] and searchTuple[1] <= tInnerRange[1] or searchTuple[0] <= tInnerRange[0] and searchTuple[1] >= tInnerRange[1]]
print(result)

====> [(5, 10), (10, 15)]

&

# In this case, 'searchTuple' is overlaping 3 ranges, and bounds don't coincide. Also, lower bounds is 'out-of-bound' and negative
tuples = [ (0, 5), (5, 10), (10, 15), (15,20) ]
searchTuple = (-3,11)
result = [tInnerRange for tInnerRange in tuples if searchTuple[0] >= tInnerRange[0] and searchTuple[0] < tInnerRange[1] or searchTuple[1] > tInnerRange[0] and searchTuple[1] <= tInnerRange[1] or searchTuple[0] <= tInnerRange[0] and searchTuple[1] >= tInnerRange[1]]
print(result)

====> [(0, 5), (5, 10), (10, 15)]

&

# In this case, 'searchTuple' is overlaping 2 ranges, lower bound coincides.
tuples = [ (0, 5), (5, 10), (10, 15), (15,20) ]
searchTuple = (5,11)
result = [tInnerRange for tInnerRange in tuples if searchTuple[0] >= tInnerRange[0] and searchTuple[0] < tInnerRange[1] or searchTuple[1] > tInnerRange[0] and searchTuple[1] <= tInnerRange[1] or searchTuple[0] <= tInnerRange[0] and searchTuple[1] >= tInnerRange[1]]
print(result)

====> [(5, 10), (10, 15)]

&

# In this case, 'searchTuple' is overlaping 1 ranges, both bounds coincide.
tuples = [ (0, 5), (5, 10), (10, 15), (15,20) ]
searchTuple = (5,10)
result = [tInnerRange for tInnerRange in tuples if searchTuple[0] >= tInnerRange[0] and searchTuple[0] < tInnerRange[1] or searchTuple[1] > tInnerRange[0] and searchTuple[1] <= tInnerRange[1] or searchTuple[0] <= tInnerRange[0] and searchTuple[1] >= tInnerRange[1]]
print(result)

====> [(5, 10)]

&

# In this case, 'searchTuple' is overlaping 2 ranges, and upper bound coincides.
tuples = [ (0, 5), (5, 10), (10, 15), (15,20) ]
searchTuple = (3,10)
result = [tInnerRange for tInnerRange in tuples if searchTuple[0] >= tInnerRange[0] and searchTuple[0] < tInnerRange[1] or searchTuple[1] > tInnerRange[0] and searchTuple[1] <= tInnerRange[1] or searchTuple[0] <= tInnerRange[0] and searchTuple[1] >= tInnerRange[1]]
print(result)

====> [(0, 5), (5, 10)]

&

# In this case, 'searchTuple' is overlaping 2 ranges, and lower bound coincides. Also, upper bounds is 'out-of-bound'.
tuples = [ (0, 5), (5, 10), (10, 15), (15,20) ]
searchTuple = (10,49)
result = [tInnerRange for tInnerRange in tuples if searchTuple[0] >= tInnerRange[0] and searchTuple[0] < tInnerRange[1] or searchTuple[1] > tInnerRange[0] and searchTuple[1] <= tInnerRange[1] or searchTuple[0] <= tInnerRange[0] and searchTuple[1] >= tInnerRange[1]]
print(result)

====> [(10, 15), (15, 20)]

&

# In this case, 'searchTuple' is overlaping 0 ranges has both bounds are 'out-of-bound'.
tuples = [ (0, 5), (5, 10), (10, 15), (15,20) ]
searchTuple = (25,49)
result = [tInnerRange for tInnerRange in tuples if searchTuple[0] >= tInnerRange[0] and searchTuple[0] < tInnerRange[1] or searchTuple[1] > tInnerRange[0] and searchTuple[1] <= tInnerRange[1] or searchTuple[0] <= tInnerRange[0] and searchTuple[1] >= tInnerRange[1]]
print(result)

====> []

Upvotes: 1

ponycat
ponycat

Reputation: 189

Answering my own question because I found an elegant solution:

tuples = [(0,5), (5,10), (10,15), (15,20)]

def overlap(tuples, search):
    res = []
    for t in tuples:
        if(t[1]>search[0] and t[0]<search[1]):
            res.append(t)
    return res

search = (1,11)
print overlap(tuples, search)

returns as expected:

[(0, 5), (5, 10), (10, 15)]

Upvotes: 4

Arvind Haran
Arvind Haran

Reputation: 720

You haven't covered the case where the search tuple entirely encloses the current tuple with which it is compared to. In your case, say (3,11) against (5,10)

Upvotes: 6

Pawel Miech
Pawel Miech

Reputation: 7822

Quick and dirty list comprehension:

>>> t = [ (0, 5), (5, 10), (10, 15), (15,20) ]
>>> o = (3,11)
>>> [(i[0],i[1]) for i in t if i[0] >= o[0] and i[0] <= o[1] or i[1] >= o[0] and i[1] <= o[1]]
#returns: 
[(0, 5), (5, 10), (10, 15)]
>>> o = (16,22)
#returns
[(15, 20)]

Upvotes: 3

Stephan
Stephan

Reputation: 18001

This method is beginner friendly and should do the trick

def findOverlap(tuples, searchTuple):
  result=[]
  for tuple in tuples:
    if searchTuple[0] in range(tuple[0],tuple[1]): #search for the first value
      result.append(tuple)
      continue
    if len(result)>0 and searchTuple[1] in range(tuple[0],tuple[1]): #search for the last value
      result.append(tuple)
      break
    if len(result)>0:
      result.append(tuple) #add all elements between first and last
  return result

range(tuple[0],tuple[1]) just returns all the numbers from one to the other, so if its looking through the (5,10) tuple it will return [5,6,7,8,9,10]

Then searchTuple[0] in range(tuple[0],tuple[1]) checks to see if the first element in searchTuple is within that range.

result.append(tuple) adds that tuple to the list of things to return from the method.

The rest of it is loop manipulation and formatting stuff.

Upvotes: 1

Related Questions