檢查範圍是否跨越路徑

我編寫了以下方法來檢查範圍列表是否跨越路徑。另一種說法是，範圍不是嵌套的。檢查範圍是否跨越路徑

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

檢查範圍是否跨越路徑

回答

相關問題