Jay Bird wrote:
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
I've tried various methods, which all fail. Does anyone have an idea
how to do this?
>>> parts = [(5, 9, "a"), (7, 10, "b"), (3, 6, "c"), (15, 20, "d"),
(18, 23, "e")]
>>> parts.sort()
>>> parts
[(3, 6, 'c'), (5, 9, 'a'), (7, 10, 'b'), (15, 20, 'd'), (18, 23, 'e')]
>>> # Merge overlapping intervals.
>>> pos = 1
>>> while pos < len(parts):
# Merge the pair in parts[pos - 1 : pos + 1] if they overlap.
p, q = parts[pos - 1 : pos + 1]
if p[1] >= q[0]:
parts[pos - 1 : pos + 1] = [(p[0], max(p[1], q[1]),
p[2] + "." + q[2])]
else:
# They don't overlap, so try the next pair.
pos += 1
>>> parts
[(3, 10, 'c.a.b'), (15, 23, 'd.e')]
--
http://mail.python.org/mailman/listinfo/python-list
