Overlap in python

[Mark Dickinson]

On Aug 4, 7:15 pm, Jay Bird <jay.bird0... at 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