On Feb 1, 2008 3:16 PM, Arnaud Delobelle <[EMAIL PROTECTED]> wrote: > On Feb 1, 2:44 pm, "Neil Cerutti" <[EMAIL PROTECTED]> wrote: > > 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 > > The total number of iterations is 1+2+...+n = n(n+1)/2 (when n is the > number of intervals) so this has quadratic behaviour regardless of > input. See my other post for a 'detailed' analysis of my solution.
But it breaks out of the inner loop as soon as ranges on the right cannot overlap. The loop is O(N) for all input if I define N as "number of overlaps", a pretty reasonable definition--it's madness to expect to report N overlaps with less than N complexity. Unless I'm making a silly mistake. Again. -- Neil Cerutti <[EMAIL PROTECTED]> -- http://mail.python.org/mailman/listinfo/python-list
