On Aug 4, 7:15 pm, Jay Bird <jay.bird0...@gmail.com> 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?
Here's an approach that might work. Turning it into a sensible
function and parsing input/massaging output properly are left
as an exercise. Blocks that just touch (e.g. (3, 6) then (6, 9))
are amalgamated; if this isn't what you want, and they should
be treated as separate instead, then replace 'Stop' with 'Finish'
(or any other string that sorts before 'Start').
input = [
('a', (5, 9)),
('b', (7, 10)),
('c', (3, 6)),
('d', (15, 20)),
('e', (18, 23)),
]
# create sorted list of points where an interval is entered or left
transitions = []
for name, (start, stop) in input:
transitions.extend([(start, 'Start', name), (stop, 'Stop', name)])
transitions.sort()
# scan list, accumulating blocks along the way.
count = 0
for i, (pt, startend, name) in enumerate(transitions):
if startend == 'Start':
if not count:
start = pt
names = []
count += 1
names.append(name)
else:
count -= 1
if not count:
print '.'.join(names), "%s--%s" % (start, pt)
The output that I get from this under Python 2.6 is:
c.a.b 3--10
d.e 15--23
--
Mark
--
http://mail.python.org/mailman/listinfo/python-list
