0

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

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

它像现在一样工作，但它似乎真的效率低下。如果这是一个常见问题或者是否有更有效的解决方案，现在有人吗？

4

2 回答 2

5

您可以排序，这将至少按排序顺序放置起点。然后，您只需要根据上一个条目检查端点；它应该更小：

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

我正在使用此处较旧的 itertools 文档页面中的window示例工具来创建滑动窗口。

此实现返回：

>>> 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-25T20:45:22.563 回答
0

我不确定您用于检测“交叉”的算法，但您可以使用理解和简化代码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-25T20:45:29.870 回答