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

Question

Скажем, у меня есть список списков с индексами [[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]] 

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

EDIT:

Другие примеры будут:

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

>>>b = [[30, 70], [25, 40]] 
>>>foo(b) 
[[25, 40]] 

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

Спасибо!

Answer 1

Чтобы удалить минимальное количество интервалов из списка таким образом, что интервалы, которые остались не перекрываются, 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, см. Fast interval intersection methodologies для использования примера.

---

Вот quicksect основанное O(n**2) реализации вышеуказанного алгоритма:

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

---

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

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 

Answer 2

1. по возрастанию сортировать по убыванию.

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

Answer 3

Я думаю, что одна проблема в вашем коде заключается в том, что она не обрабатывает ситуацию, когда один список содержит другой. Например, [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 

Answer 4

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

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

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

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

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

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

Answer 5

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

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