4

假设我有一个完整的元组列表，表示“从”和“到”时间：

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

我希望能够检索与给定元组重叠的元组列表：

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

此代码应返回以下列表：

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

虽然 (16, 22) 的 searchTuple 应该只返回最后一个元组 (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

但是，实施此操作后得到的结果最终给了我错误的结果……我的想法哪里错了？

4

6 回答 6

6

您还没有涵盖搜索元组完全包含与之比较的当前元组的情况。在你的情况下，说（3,11）对（5,10）

于 2013-07-25T20:19:39.197 回答
4

回答我自己的问题，因为我找到了一个优雅的解决方案：

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)]
于 2013-07-25T20:16:19.890 回答
3

快速而肮脏的列表理解：

>>> 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)]
于 2013-07-25T20:13:01.693 回答
2

这是您可以编写的最愚蠢的代码：

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

我希望我没有弄错索引！如果对元组进行排序，则可以通过更智能的搜索来提高代码性能。几年前，我在尝试学习算法时遇到了类似的问题。所以我想这是一种流行的问题，你可以通过谷歌搜索找到有效的代码

于 2013-07-25T20:04:07.030 回答
1

这种方法对初学者友好，应该可以解决问题

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)将该元组添加到要从该方法返回的事物列表中。

剩下的就是循环操作和格式化的东西。

于 2013-07-25T19:56:49.910 回答
1

这是我的解决方案：

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)

====> []
于 2013-07-25T20:16:20.150 回答