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

[Arnaud Delobelle]

On Feb 1, 2:44 pm, "Neil Cerutti" <mr.ceru... at gmail.com> wrote:
> On Feb 1, 2008 8:28 AM, Arnaud Delobelle <arno... at googlemail.com> 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

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.

--
Arnaud