Python – удаление перекрывающихся списков

Скажем, у меня есть список списков с индексами [[start, end], [start1, end1], [start2, end2]] .

Как например:

[[0, 133], [78, 100], [25, 30]] .

Как мне получить проверку на совпадение между списками и удалить список с большей длиной каждый раз? Так:

 >>> list = [[0, 133], [78, 100], [25, 30]] >>> foo(list) [[78, 100], [25, 30]] 

Это то, что я пытался сделать до сих пор:

 def cleanup_list(list): i = 0 c = 0 x = list[:] end = len(x) while i < end-1: for n in range(x[i][0], x[i][1]): if n in range(x[i+1][0], x[i+1][1]): list.remove(max(x[i], x[i+1])) i +=1 return list 

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

  >>>cleanup_list([[0,100],[9,10],[12,90]]) [[0, 100], [12, 90]] 

Любая помощь будет оценена!

РЕДАКТИРОВАТЬ:

Другие примеры:

 >>>a = [[0, 100], [4, 20], [30, 35], [30, 78]] >>>foo(a) [[4, 20], [30, 35]] >>>b = [[30, 70], [25, 40]] >>>foo(b) [[25, 40]] 

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

Благодаря!!

Чтобы удалить минимальное количество интервалов из списка, чтобы оставшиеся интервалы не перекрывались, существует алгоритм O(n*log n) :

 def maximize_nonoverlapping_count(intervals): # sort by the end-point L = sorted(intervals, key=lambda (start, end): (end, (end - start)), reverse=True) # O(n*logn) iv = build_interval_tree(intervals) # O(n*log n) result = [] while L: # until there are intervals left to consider # pop the interval with the smallest end-point, keep it in the result result.append(L.pop()) # O(1) # remove intervals that overlap with the popped interval overlapping_intervals = iv.pop(result[-1]) # O(log n + m) remove(overlapping_intervals, from_=L) return result 

Он должен давать следующие результаты:

 f = maximize_nonoverlapping_count assert f([[0, 133], [78, 100], [25, 30]]) == [[25, 30], [78, 100]] assert f([[0,100],[9,10],[12,90]]) == [[9,10], [12, 90]] assert f([[0, 100], [4, 20], [30, 35], [30, 78]]) == [[4, 20], [30, 35]] assert f([[30, 70], [25, 40]]) == [[25, 40]] 

Для этого требуется структура данных, которая может находить в O(log n + m) время все интервалы, которые перекрываются с заданным интервалом, например IntervalTree . Существуют реализации, которые можно использовать на Python, например, quicksect.py , см. quicksect.py пересечения с быстрым интервалом для использования примера.


Ниже приведена реализация quicksect O(n**2) основанная на quicksect :

 from quicksect import IntervalNode class Interval(object): def __init__(self, start, end): self.start = start self.end = end self.removed = False def maximize_nonoverlapping_count(intervals): intervals = [Interval(start, end) for start, end in intervals] # sort by the end-point intervals.sort(key=lambda x: (x.end, (x.end - x.start))) # O(n*log n) tree = build_interval_tree(intervals) # O(n*log n) result = [] for smallest in intervals: # O(n) (without the loop body) # pop the interval with the smallest end-point, keep it in the result if smallest.removed: continue # skip removed nodes smallest.removed = True result.append([smallest.start, smallest.end]) # O(1) # remove (mark) intervals that overlap with the popped interval tree.intersect(smallest.start, smallest.end, # O(log n + m) lambda x: setattr(x.other, 'removed', True)) return result def build_interval_tree(intervals): root = IntervalNode(intervals[0].start, intervals[0].end, other=intervals[0]) return reduce(lambda tree, x: tree.insert(x.start, x.end, other=x), intervals[1:], root) 

Примечание: сложность времени в худшем случае – O(n**2) для этой реализации, потому что интервалы отмечены только как удаленные, например, представьте такие входные intervals которые len(result) == len(intervals) / 3 и были len(intervals) / 2 интервала, которые охватывают весь диапазон, тогда tree.intersect() будет называться n/3 раза, и каждый вызов будет выполнять x.other.removed = True по крайней мере, n/2 раза, т. е. n*n/6 Всего операций:

 n = 6 intervals = [[0, 100], [0, 100], [0, 100], [0, 10], [10, 20], [15, 40]]) result = [[0, 10], [10, 20]] 

Вот реализация O(n log n) на основе banyan :

 from banyan import SortedSet, OverlappingIntervalsUpdator # pip install banyan def maximize_nonoverlapping_count(intervals): # sort by the end-point O(n log n) sorted_intervals = SortedSet(intervals, key=lambda (start, end): (end, (end - start))) # build "interval" tree O(n log n) tree = SortedSet(intervals, updator=OverlappingIntervalsUpdator) result = [] while sorted_intervals: # until there are intervals left to consider # pop the interval with the smallest end-point, keep it in the result result.append(sorted_intervals.pop()) # O(log n) # remove intervals that overlap with the popped interval overlapping_intervals = tree.overlap(result[-1]) # O(m log n) tree -= overlapping_intervals # O(m log n) sorted_intervals -= overlapping_intervals # O(m log n) return result 

Примечание: в этой реализации рассматриваются перекрывающиеся интервалы [0, 10] и [10, 20] :

 f = maximize_nonoverlapping_count assert f([[0, 100], [0, 10], [11, 20], [15, 40]]) == [[0, 10] ,[11, 20]] assert f([[0, 100], [0, 10], [10, 20], [15, 40]]) == [[0, 10] ,[15, 40]] 

sorted_intervals и tree могут быть объединены:

 from banyan import SortedSet, OverlappingIntervalsUpdator # pip install banyan def maximize_nonoverlapping_count(intervals): # build "interval" tree sorted by the end-point O(n log n) tree = SortedSet(intervals, key=lambda (start, end): (end, (end - start)), updator=OverlappingIntervalsUpdator) result = [] while tree: # until there are intervals left to consider # pop the interval with the smallest end-point, keep it in the result result.append(tree.pop()) # O(log n) # remove intervals that overlap with the popped interval overlapping_intervals = tree.overlap(result[-1]) # O(m log n) tree -= overlapping_intervals # O(m log n) return result 

Это, возможно, не самое быстрое решение, но действительно многословное и ясное – я думаю.

 a = [[2,100], [4,10], [77,99], [38,39], [44,80], [69,70], [88, 90]] # build ranges first def expand(list): newList = [] for r in list: newList.append(range(r[0], r[1] + 1)) return newList def compare(list): toBeDeleted = [] for index1 in range(len(list)): for index2 in range(len(list)): if index1 == index2: # we dont want to compare ourselfs continue matches = [x for x in list[index1] if x in list[index2]] if len(matches) != 0: # do we have overlap? ## compare lengths and get rid of the longer one if len(list[index1]) > len(list[index2]): toBeDeleted.append(index1) break elif len(list[index1]) < len(list[index2]): toBeDeleted.append(index2) # distinct toBeDeleted = [ toBeDeleted[i] for i,x in enumerate(toBeDeleted) if x not in toBeDeleted[i+1:]] print len(list) # remove items for i in toBeDeleted[::-1]: del list[i] return list print(compare(expand(a))) 

Я думаю, что в вашем коде есть одна проблема: он не справляется с ситуацией, когда один список содержит другой. Например, [0,100] содержит [9,10] . Когда вы петли n в [0,100], а n входит в [9,10], запускается оператор условия, if n in range(x[i+1][0], x[i+1][1]) . Тогда встроенная функция max будет сравнивать [0, 100] и [9, 10] , и, к сожалению, max вернет [9,10] поскольку сравнивает первое число в списке. Таким образом, вы удаляете неправильный элемент.

Я пробую еще один способ добиться желаемого эффекта. Вместо того, чтобы манипулировать самим списком, я создаю новый список. Условно добавление нового элемента к нему, если оно соответствует нашим требованиям.

 def cleanup_list(lists): ranges = [] for l in lists: to_insert = True for i in ranges: r = range(i[0],i[1]) # if l overlaps with i, but l does not contain i if l[0] in r or l[1] in r: if (l[1]-l[0]) < len(r): ranges.remove(i) else: to_insert = False # l contains i if l[0]<i[0] and l[1]>i[1]: to_insert = False if to_insert: ranges.append(l) return ranges 
  1. по возрастанию сортировать все элементы по длине.

  2. добавьте их в дерево сегментов и игнорируйте перекрывающиеся элементы.

В общем случае два интервала перекрываются, если:

 min([upperBoundOfA, upperBoundOfB]) >= max([lowerBoundOfA, lowerBoundOfB]) 

Если это так, объединение этих интервалов:

 (min([lowerBoundOfA, lowerBoundOfB]), max([upperBoundOfA, upperBoundOfB]) 

Аналогично, пересечение этих интервалов будет:

 (min([upperBoundOfA, upperBoundOfB]), max([lowerBoundOfA, lowerBoundOfB]))