如何找到重疊的給定範圍內的元組

Question

說我有一個完整的元組「從」表示的列表和「到」時間的元組：

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 

我希望我沒有搞錯的指標！ 如果您對元組進行排序，您可以通過更智能的搜索來提高代碼性能。 幾年前，當我試圖學習算法時，我遇到了類似的問題。所以我想這是一個受歡迎的類型的問題，你可以通過google搜索找到有效的代碼

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,10）針對（5,10）