How to identify which numbers in a list are within each others' range

[Neil Cerutti]

On Feb 1, 2008 3:16 PM, Arnaud Delobelle <arnodel at googlemail.com> wrote:
> On Feb 1, 2:44 pm, "Neil Cerutti" <mr.ceru... at gmail.com> 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 <mr.cerutti+python at gmail.com>