In <78d86d92-d373-4163-a418-600a3eb36...@o15g2000yqm.googlegroups.com> Mark
Dickinson <dicki...@gmail.com> writes:
>On Aug 4, 7:15=A0pm, 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. =A0For example, here would be my input:
>>
>> part name =A0 location
>> a =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A05-9
>> b =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A07-10
>> c =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A03-6
>> d =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A015-20
>> e =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A018-23
>>
>> And here is what I need for an output:
>> part name =A0 location
>> c.a.b =A0 =A0 =A0 =A0 =A0 =A03-10
>> d.e =A0 =A0 =A0 =A0 =A0 =A0 =A0 15-23
>>
>> I've tried various methods, which all fail. =A0Does 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 =3D [
> ('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 =3D []
>for name, (start, stop) in input:
> transitions.extend([(start, 'Start', name), (stop, 'Stop', name)])
>transitions.sort()
># scan list, accumulating blocks along the way.
>count =3D 0
>for i, (pt, startend, name) in enumerate(transitions):
> if startend =3D=3D 'Start':
> if not count:
> start =3D pt
> names =3D []
> count +=3D 1
> names.append(name)
> else:
> count -=3D 1
> if not count:
> print '.'.join(names), "%s--%s" % (start, pt)
Very cool.
kynn
--
http://mail.python.org/mailman/listinfo/python-list
