# Overlap in python

Gregor Lingl gregor.lingl at aon.at
Tue Aug 4 21:57:40 CEST 2009

```Jay Bird schrieb:
> Hi everyone,
>
> I've been trying to figure out a simple algorithm on how to combine a
> list of parts that have 1D locations that overlap into a non-
> overlapping list.  For example, here would be my input:
>
> part name   location
> a                  5-9
> b                  7-10
> c                  3-6
> d                  15-20
> e                  18-23
>
> And here is what I need for an output:
> part name   location
> c.a.b            3-10
> d.e               15-23
>

Suppose you have your data given as a dictionary:

data = {'a':(5,9),
'b':(7,10),
'c':(3,6),
'd':(15,20),
'e':(18,23)}

Then the following not particularly elegant
but very simple and straight forward

def values(key):
return set(range(data[key][0], data[key][1]+1))

keys = list(data.keys())
result = []
while keys:
k = [keys[0]]
keys = keys[1:]
v = values(k[0])
for l in keys[:]:
if v.intersection(values(l)):
v.update(values(l))
k.append(l)
keys.remove(l)
result.append((k,v))

# print(result) ## if you like

for k, v in result:
print(".".join(sorted(k)), "%d-%d" % (min(v), max(v)))

Regards,
Gregor

> I've tried various methods, which all fail.  Does anyone have an idea
> how to do this?
>
> Thank you very much!
> Jay

```