Wie eine Reihe von überlappenden Bereichen in nicht überlappende Bereiche zu unterteilen?

Question

Angenommen, Sie haben eine Reihe von Bereichen haben:

• 0 bis 100: 'a'
• 0-75: 'b'
• 95-150: 'c'
• 120-130: 'd'

Offensichtlich überlappen diese Bereiche an bestimmten Punkten. Wie würden Sie diese Bereiche sezieren eine Liste der nicht-überlappende Bereiche zu erzeugen, unter Beibehaltung Informationen mit ihren ursprünglichen Bereich zugeordnet (in diesem Fall, den Brief nach Bereich)?

Zum Beispiel kann die Ergebnisse der oben nach dem Algorithmus ausgeführt wäre:

• 0-75: 'a', 'b'
• 76-94: 'a'
• 95-100: 'a', 'c'
• 101-119: 'c'
• 120-130: 'c', 'd'
• 131-150: 'c'

Answer 1

hatte ich die gleiche Frage, wenn ein Programm schreiben, zu mischen (teilweise überlappende) Audio-Samples.

Was ich tat, war hinzufügen ein „Ereignis Start“ und „Stop Event“ (für jedes Element) zu einer Liste, sortieren Sie die Liste nach dem Zeitpunkt, und dann, um verarbeiten. Sie könnten das gleiche tun, außer mit einem ganzzahligen Punkt anstelle einer Zeit, und statt Misch Sounds, die Sie Symbole auf den Satz würde man zu einer Reihe entspricht. Ob Sie leere Bereiche erzeugen würden oder weglassen nur würde sie optional sein.

Edit Vielleicht haben einige Code ...

# input = list of (start, stop, symbol) tuples
points = [] # list of (offset, plus/minus, symbol) tuples
for start,stop,symbol in input:
    points.append((start,'+',symbol))
    points.append((stop,'-',symbol))
points.sort()

ranges = [] # output list of (start, stop, symbol_set) tuples
current_set = set()
last_start = None
for offset,pm,symbol in points:
    if pm == '+':
         if last_start is not None:
             #TODO avoid outputting empty or trivial ranges
             ranges.append((last_start,offset-1,current_set))
         current_set.add(symbol)
         last_start = offset
    elif pm == '-':
         # Getting a minus without a last_start is unpossible here, so not handled
         ranges.append((last_start,offset-1,current_set))
         current_set.remove(symbol)
         last_start = offset

# Finish off
if last_start is not None:
    ranges.append((last_start,offset-1,current_set))

Völlig ungetestet, offensichtlich.

Answer 2

Ich würde sagen, eine Liste der Endpunkte erstellen und sortieren, auch Index die Liste der Bereiche, die durch Start- und Endpunkte. Dann durchlaufen die Liste der sortierten Endpunkte, und für jeden einzelnen, die Bereiche zu überprüfen, um zu sehen, welche beginnen / an diesem Punkt gestoppt wird.

Dies ist wahrscheinlich besser in Code dargestellt ..., wenn Ihre Bereiche von Tupeln dargestellt werden:

ranges = [(0,100,'a'),(0,75,'b'),(95,150,'c'),(120,130,'d')]
endpoints = sorted(list(set([r[0] for r in ranges] + [r[1] for r in ranges])))
start = {}
end = {}
for e in endpoints:
    start[e] = set()
    end[e] = set()
for r in ranges:
    start[r[0]].add(r[2])
    end[r[1]].add(r[2])
current_ranges = set()
for e1, e2 in zip(endpoints[:-1], endpoints[1:]):
    current_ranges.difference_update(end[e1])
    current_ranges.update(start[e1])
    print '%d - %d: %s' % (e1, e2, ','.join(current_ranges))

Auch wenn im Rückblick auf diese suchen, würde ich überrascht, wenn es nicht war ein effizienter (oder zumindest sauberer aussehende) Art und Weise, es zu tun.

Answer 3

Was Sie beschreiben, ist ein Beispiel der Mengenlehre. Für einen allgemeinen Algorithmus zur Berechnung Gewerkschaften, Kreuzungen und Unterschiede von Sätzen sehen:

www.gvu.gatech.edu/~jarek/graphics /papers/04PolygonBooleansMargalit.pdf

Während das Papier bei Grafiken gezielt wird, ist es für allgemeine Mengenlehre als auch. Nicht gerade leichte Lektüre Material.

Answer 4

Pseudocode:

unusedRanges = [ (each of your ranges) ]
rangesInUse = []
usedRanges = []
beginningBoundary = nil

boundaries = [ list of all your ranges' start and end values, sorted ]
resultRanges = []

for (boundary in boundaries) {
    rangesStarting = []
    rangesEnding = []

    // determine which ranges begin at this boundary
    for (range in unusedRanges) {
        if (range.begin == boundary) {
            rangesStarting.add(range)
        }
    }

    // if there are any new ones, start a new range
    if (rangesStarting isn't empty) {
        if (beginningBoundary isn't nil) {
            // add the range we just passed
            resultRanges.add(beginningBoundary, boundary - 1, [collected values from rangesInUse])
        }

        // note that we are starting a new range
        beginningBoundary = boundary

        for (range in rangesStarting) {
            rangesInUse.add(range)
            unusedRanges.remove(range)
        }
    }

    // determine which ranges end at this boundary
    for (range in rangesInUse) {
        if (range.end == boundary) {
            rangesEnding.add(range)
        }
    }

    // if any boundaries are ending, stop the range
    if (rangesEnding isn't empty) {
        // add the range up to this boundary
        resultRanges.add(beginningBoundary, boundary, [collected values from rangesInUse]

        for (range in rangesEnding) {
            usedRanges.add(range)
            rangesInUse.remove(range)
        }

        if (rangesInUse isn't empty) {
            // some ranges didn't end; note that we are starting a new range
            beginningBoundary = boundary + 1
        }
        else {
            beginningBoundary = nil
        }
    }
}

Unit-Test:

Am Ende resultRanges sollten die Ergebnisse haben Sie suchen, unusedRanges und rangesInUse sollte leer sein sollte beginningBoundary Null sein, und usedRanges enthalten sollte, was enthalten unusedRanges verwendet (aber range.end sortiert).

Answer 5

Eine ähnliche Antwort auf Edmunds, getestet, einschließlich der Unterstützung für Intervalle wie (1,1):

class MultiSet(object):
    def __init__(self, intervals):
        self.intervals = intervals
        self.events = None

    def split_ranges(self):
        self.events = []
        for start, stop, symbol in self.intervals:
            self.events.append((start, True, stop, symbol))
            self.events.append((stop, False, start, symbol))

        def event_key(event):
            key_endpoint, key_is_start, key_other, _ = event
            key_order = 0 if key_is_start else 1
            return key_endpoint, key_order, key_other

        self.events.sort(key=event_key)

        current_set = set()
        ranges = []
        current_start = -1

        for endpoint, is_start, other, symbol in self.events:
            if is_start:
                if current_start != -1 and endpoint != current_start and \
                       endpoint - 1 >= current_start and current_set:
                    ranges.append((current_start, endpoint - 1, current_set.copy()))
                current_start = endpoint
                current_set.add(symbol)
            else:
                if current_start != -1 and endpoint >= current_start and current_set:
                    ranges.append((current_start, endpoint, current_set.copy()))
                current_set.remove(symbol)
                current_start = endpoint + 1

        return ranges


if __name__ == '__main__':
    intervals = [
        (0, 100, 'a'), (0, 75, 'b'), (75, 80, 'd'), (95, 150, 'c'), 
        (120, 130, 'd'), (160, 175, 'e'), (165, 180, 'a')
    ]
    multiset = MultiSet(intervals)
    pprint.pprint(multiset.split_ranges())


[(0, 74, {'b', 'a'}),
 (75, 75, {'d', 'b', 'a'}),
 (76, 80, {'d', 'a'}),
 (81, 94, {'a'}),
 (95, 100, {'c', 'a'}),
 (101, 119, {'c'}),
 (120, 130, {'d', 'c'}),
 (131, 150, {'c'}),
 (160, 164, {'e'}),
 (165, 175, {'e', 'a'}),
 (176, 180, {'a'})]