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

[Paul McGuire]

Hi,

I have a list of numbers each with a +/- margin of error.  I need to
identify which ones overlab each other.

Here's my proposal, using arithmetic instead of sets. Looking at the
problem graphically, I drew different numberlines:

--XXX-----XXXXXXXXX----XXXXXX-------
--------XXXX------------------------

I test the overlapping by drawing a line from the min of the lower
range to the max of each upper range, and from the max of the lower
range to the min of each upper range. Overlap occurs if one delta is
positive and the other negative. Multiply the two deltas, and overlap
occurs if the product is negative. If ranges are inclusive instead of
exclusive of the bounds, then a 0 product also counts as overlap.

# don't name variables 'list' or 'dict' or 'int' or 'str' or 'tuple'
ranges = [
(55, 58, 52),
(20, 22, 18),
(17, 21, 13),
(60, 63, 57),
]

def overlap(r1, r2):
_,max1,min1 = r1
_,max2,min2 = r2
# if max1==min2 or max2==min1 counts as overlap, change '<' to
'<='
return (max2-min1)*(min2-max1) < 0

for i,r1 in enumerate(ranges[:-1]):
for r2 in ranges[i+1:]:
if overlap(r1,r2):
print r1, "overlaps", r2
else:
print r1, "does not overlap", r2

Prints:
(55, 58, 52) does not overlap (20, 22, 18)
(55, 58, 52) does not overlap (17, 21, 13)
(55, 58, 52) overlaps (60, 63, 57)
(20, 22, 18) overlaps (17, 21, 13)
(20, 22, 18) does not overlap (60, 63, 57)
(17, 21, 13) does not overlap (60, 63, 57)


-- Paul

 

[Arnaud Delobelle]

Arnaud Delobelle wrote:

(...)

from itertools import chain

def overlaps(lst):
    bounds = chain(*(((x[1],i), (x[2], i)) for i,x in enumerate(lst)))

imho, this is a uselessly painful equivalent of

       bounds = ((x[k],i) for i,x in enumerate(lst) for k in (1,2))

Cheers, BB

I did mention that it was awkward (but at the time I just wrote what
came to mind) - thank you for providing a much improved version.

It doesn't deter from the fact that the algorithm is of optimal
complexity (modulo sorting of the list).