[ Checking if ranges cross paths ]
I wrote the following method to check if a list of ranges cross paths. Another way of saying this is that the ranges are not nested.
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] b = lst[i] x = lst[j] y = lst[j] #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
The first should return false and the second true.
It works as it is now, but it seems really inefficient. Does anyone now if this is a common problem or if there is a more efficient solution?
You could sort, which will put at least the starting points in sorted order. Then you only really need to check the endpoint against the previous entry; it should be smaller:
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 < b for a, b in window(sorted(lst)))
I'm using the
window example tool from an older itertools documentation page here to create the sliding window.
This implementation returns:
>>> def check_ranges(lst): ... return any(a < b 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
It is not entirely clear if matching end points would be a problem or not; if they are not, then you could change the
< to a
<= test instead.
I'm not sure about the algorithm which you are using to detect "crossover", but you could simplify your code using a comprehension and
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:])