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
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
More information about the Python-list
mailing list