On Feb 1, 2008 8:28 AM, Arnaud Delobelle <[EMAIL PROTECTED]> wrote:
> Yours is O(n^2) and \Omega(n^2). I think mine is O(max(c, nlogn))
> (assuming constant time access for dictionaries, but 'inside' could be
> replaced with a list) where c is the number of overlaps. I'll try to
> post a proof later (if it's true!). So if we are in a situation where
> overlaps are rare, it is in practice O(nlogn).
Here's another contender, basically the same as yours, but spelled
without iterators.
def overlaps(eranges):
"""Determine, from a list of numbers and a +/- range of uncertainty, which
number ranges overlap each other. Return the overlapping range indexes as
a list of overlapping pairs.
>>> sorted(overlaps(((55, 3), (20, 2), (17, 4), (60, 3))))
[(0, 3), (1, 2)]
"""
d = [(r[0] - r[1], r[0] + r[1], i) for i, r in enumerate(eranges)]
d.sort()
rv = []
x = 0
while x < len(d):
minx, maxx, ix = d[x]
y = x+1
while y < len(d):
miny, maxy, iy = d[y]
if miny < maxx:
rv.append((ix, iy) if ix < iy else (iy, ix))
else:
break
y += 1
x += 1
return rv
--
Neil Cerutti <[EMAIL PROTECTED]>
--
http://mail.python.org/mailman/listinfo/python-list
