Overlap in python

[Gregor Lingl]

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