Comment diviser un ensemble de plages superposées en plages non superposées?

Question

Disons que vous avez un ensemble de plages:

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

Évidemment, ces plages se chevauchent à certains moments. Comment disséqueriez-vous ces plages pour produire une liste de plages ne se chevauchant pas, tout en conservant les informations associées à leur plage d'origine (dans ce cas, la lettre après la plage)?

Par exemple, les résultats ci-dessus après l'exécution de l'algorithme seraient:

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

Answer 1

J'avais la même question lors de l'écriture d'un programme destiné à mélanger des échantillons audio (se chevauchant partiellement).

J'ai ajouté un " événement de départ " et " arrêter l'événement " (pour chaque élément) dans une liste, triez la liste par heure, puis traitez-la dans l'ordre. Vous pouvez faire la même chose, sauf que vous utilisez un point entier au lieu d'une heure. Au lieu de mélanger des sons, vous ajoutez des symboles à l'ensemble correspondant à une plage. Que vous souhaitiez générer des plages vides ou simplement les omettre serait facultatif.

Modifier Peut-être du 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))

Totalement non testé, évidemment.

Answer 2

Je dirais de créer et de trier une liste des noeuds finaux, puis d'indexer la liste des plages par des points de départ et d'arrivée. Parcourez ensuite la liste des ordinateurs d'extrémité triés et, pour chacun d'entre eux, vérifiez les plages pour voir celles qui démarrent / s'arrêtent à cet endroit.

Ceci est probablement mieux représenté dans le code ... si vos gammes sont représentées par des n-uplets:

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))

Bien que je regarde cela rétrospectivement, je serais surpris de constater qu’il n’y avait pas de moyen plus efficace (ou au moins plus propre) de le faire.

Answer 3

Ce que vous décrivez est un exemple de théorie des ensembles. Pour un algorithme général permettant de calculer les unions, les intersections et les différences d’ensembles, voir:

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

Bien que le document vise les graphiques, il est également applicable à la théorie des ensembles générale. Ce n'est pas vraiment du matériel de lecture léger.

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
        }
    }
}

Test unitaire:

À la fin, resultRanges devrait avoir les résultats que vous recherchez,. p>

Answer 5

Une réponse similaire à Edmunds, testée, incluant le support d'intervalles comme (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'})]