On Dec 14, 10:45 am, Breal <[EMAIL PROTECTED]> wrote:
> I have a list that looks like the following
> [(100000, 100010), (100005, 100007), (100009, 100015)]
>
> I would like to be able to determine which of these overlap each
> other. So, in this case, tuple 1 overlaps with tuples 2 and 3.
Your definition of overlaps appears to be reflexive, so the following
two results follow automatically.
> Tuple
> 2 overlaps with 1. Tuple 3 overlaps with tuple 1.
>
> In my scenario I would have hundreds, if not thousands of these
> ranges. Any nice pythonic way to do this?
Probably not.
Just ensure that (a) your time intervals (start, end) obey start <=
end (b) your list of intervals is sorted, then get stuck in:
# tested no more that what you see
alist = [(100000, 100010), (100005, 100007), (100009, 100015),
(100016, 100017), (100016, 100018)]
n = len(alist)
for i in xrange(n - 1):
istart, iend = alist[i]
for j in xrange(i + 1, n):
jstart, jend = alist[j]
if jstart > iend:
break
print "Overlap:", i, alist[i], j, alist[j]
After the sort, it looks like O(N**2) in worst case, but you could get
a few zillion results done while you are hunting for a faster
algorithm.
Cheers,
John
--
http://mail.python.org/mailman/listinfo/python-list
