Как разделить набор перекрывающихся диапазонов на непересекающиеся диапазоны?

Question

Допустим, у вас есть набор диапазонов:

• 0–100:'а'
• 0–75:'б'
• 95 – 150:'с'
• 120 - 130:'д'

Очевидно, что эти диапазоны в определенных точках перекрываются.Как бы вы разобрали эти диапазоны, чтобы получить список непересекающихся диапазонов, сохранив при этом информацию, связанную с их исходным диапазоном (в данном случае букву после диапазона)?

Например, результаты вышеизложенного после запуска алгоритма будут такими:

• 0–75:'а', 'б'
• 76 - 94:'а'
• 95 - 100:'а', 'в'
• 101 - 119:'с'
• 120 - 130:'CD'
• 131 - 150:'с'

Answer 1

У меня возник тот же вопрос при написании программы для микширования (частично перекрывающихся) аудиосэмплов.

Я добавил в список «начальное событие» и «конечное событие» (для каждого элемента), отсортировал список по моменту времени, а затем обработал его по порядку.Вы могли бы сделать то же самое, но вместо времени использовать целочисленную точку и вместо смешивания звуков добавлять символы в набор, соответствующий диапазону.Будете ли вы создавать пустые диапазоны или просто опускать их, необязательно.

Edit Возможно какой-то код...

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

Совершенно непроверенный, очевидно.

Answer 2

Я бы сказал, создайте список конечных точек и отсортируйте его, а также проиндексируйте список диапазонов по начальной и конечной точкам.Затем просмотрите список отсортированных конечных точек и для каждой из них проверьте диапазоны, чтобы увидеть, какие из них начинаются/останавливаются в этой точке.

Вероятно, это лучше представлено в коде...если ваши диапазоны представлены кортежами:

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

Хотя, глядя на это ретроспективно, я был бы удивлён, если бы не существовало более эффективного (или, по крайней мере, более чистого) способа сделать это.

Answer 3

То, что вы описываете, является примером теории множеств.Общий алгоритм вычисления объединений, пересечений и разностей множеств см.:

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

Хотя статья ориентирована на графику, она применима и к общей теории множеств.Не совсем легкий материал для чтения.

Answer 4

Псевдокод:

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

Модульный тест:

В конце resultRanges должны содержать результаты, которые вы ищете, unusedRanges и rangesInUse должны быть пустыми, BeginBoundary должен быть нулевым, а UsedRanges должен содержать то, что раньше содержал unusedRanges (но отсортировано по range.end).

Answer 5

Аналогичный ответ Эдмундсу, проверенный, включая поддержку таких интервалов, как (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'})]