检查范围是否跨越路径

我编写了以下方法来检查范围列表是否跨越路径。另一种说法是，范围不是嵌套的。检查范围是否跨越路径

def check_ranges(lst): 
    for i in range(len(lst)): 
     for j in range(i+1,len(lst)): 
      # (a,b) and (x,y) are being compared 
      a = lst[i][0] 
      b = lst[i][1] 
      x = lst[j][0] 
      y = lst[j][1] 

      #both of these conditions mean that they cross 
      if x < a and b > y: 
       return True 
      if x > a and b < y: 
       return True 
    return False

第一个应该返回false，第二个true。

check_ranges([(7,16),(6,17),(5,18),(4,19)]) 
check_ranges([(5,16),(6,17),(5,18),(4,19)])

它的工作原理与现在一样，但看起来效率很低。如果这是一个常见问题，或者是否有更高效的解决方案，现在是否有人？

来源

2012-11-25 russjohnson09

我不知道我理解你想要的结果。为什么第一个失败？ '（7,16）'是'（6,17）'的一个子集。它应该是为了？每个连续范围应该是前一个超集吗？ – jdi

您可以排序，这将至少将排序的起点。那么你只需要根据以前的条目检查端点;它应该是更小：

from itertools import islice 

def window(seq, n=2): 
    "Returns a sliding window (of width n) over data from the iterable" 
    " s -> (s0,s1,...s[n-1]), (s1,s2,...,sn), ...     " 
    it = iter(seq) 
    result = tuple(islice(it, n)) 
    if len(result) == n: 
     yield result  
    for elem in it: 
     result = result[1:] + (elem,) 
     yield result 

def check_ranges(lst): 
    return any(a[1] < b[1] for a, b in window(sorted(lst)))

我使用window example tool从旧itertools文档页面在这里创造了滑动窗口。

此实现返回：

>>> def check_ranges(lst): 
...  return any(a[1] < b[1] for a, b in window(sorted(lst))) 
... 
>>> check_ranges([(7,16),(6,17),(5,18),(4,19)]) 
False 
>>> check_ranges([(5,16),(6,17),(5,18),(4,19)]) 
True

这是不完全清楚，如果匹配终点将是一个问题或没有;如果不是，那么您可以将<更改为<=测试。

来源

2012-11-25 20:45:22

我不知道你正在使用，以检测“交叉”的算法，但你可以使用一个理解和any简化代码：

return any((x<a and b<y or x>a and b<y) 
      for i,(a,b) in enumerate(lst) 
      for (x,y) in lst[i:])

来源

2012-11-25 20:45:29

检查范围是否跨越路径

回答

相关问题