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),

Then the following not particularly elegant
but very simple and straight forward
algorithm will solve your problem:

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)):

# print(result) ## if you like

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


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

More information about the Python-list mailing list