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

Question

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

• 0 - 100: 'а'
• 0 - 75: 'B'
• 95 - 150: 'с'
• 120 - 130 : 'd'

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

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

• 0 - 75: 'а', 'б'
• 76 - 94: 'а'
• 95 - 100: 'а', 'с'
• 101 - 119: 'с'
• 120 - 130: 'с', 'd'
• 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

псевдокод:

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 должны быть пустыми, beginningBoundary должен быть нулевым, и usedRanges должны содержат то, что unusedRanges использовалось для хранения (но отсортировано по range.end).

Answer 4

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

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

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