Как найти кортежи, которые перекрывают заданный диапазон кортеж

Question

Say У меня есть список полного кортежей, обозначающих «от» и «до» Время:

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

И я хочу, чтобы иметь возможность получить список кортежа, которые пересекаются с заданной кортежем:

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

Этот код должен вернуть следующий список:

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

в то время как searchTuple (16 , 22) должен возвращать только последний кортеж (15,20)

Каков наиболее эффективный способ кодирования этого поиска? Я пробовал разные вещи, но у меня проблемы с правильной работой алгоритма. Я полагал, что следующие различные «перекрывается», что я заинтересован в ловле:

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 

Однако результаты, которые я получил после реализации этого в конечном итоге дает мне неправильные результаты ... Где мое мышление не так?

Answer 1

Отвечая на мой собственный вопрос, потому что я нашел элегантное решение:

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) 

возвращается, как и ожидалось:

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

Answer 2

Этот метод начинающий дружелюбным и должен сделать трюк

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]) просто возвращает все числа от одного к другому, так что если его просматривал (5,10) кортеж вернет [5,6,7,8,9,10]

Тогда searchTuple[0] in range(tuple[0],tuple[1]) проверяет, находится ли первый элемент в searchTuple внутри этого диапазона.

result.append(tuple) добавляет этот кортеж в список вещей, возвращаемых методом.

Остальное - манипуляции с контуром и форматирование.

Answer 3

Это тупой код вы можете написать:

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 

Я надеюсь, что я не ошибаюсь, индексов! , если вы сортируете кортежи, вы можете улучшить производительность кода, сделав более разумный поиск. Я столкнулся с подобной проблемой много лет назад, когда пытался изучать алгоритмы.так что я предполагаю, что это популярный тип вопроса, и вы можете найти эффективные коды, прибегая к помощи

Answer 4

Быстрый и грязный список понимание:

>>> 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)] 

Answer 5

Это мое решение:

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]] 

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

Ниже приведены некоторые выходные данные для различных значений '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) 

====> [] 

Answer 6

Вы не рассмотрели случай, когда поисковый кортеж полностью охватывает текущий кортеж, с которым он сравнивается. В вашем случае, скажем, (3,11) против (5,10)