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

[Neil Cerutti]

On Feb 1, 2008 8:28 AM, Arnaud Delobelle <arnodel 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

-- 
Neil Cerutti <mr.cerutti+python at gmail.com>