Python - usuwanie nakładających się list

Question

Powiedz, że mam listę list z indeksami [[start, end], [start1, end1], [start2, end2]].

Jak na przykład:

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

W jaki sposób uzyskać kontrolę nad nakładaniem się między listami i za każdym razem usuwać listę o większej długości? Więc:

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

To, co starałem się zrobić do tej pory:

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 

Ale oprócz ich rodzaju zawiłe to nie działa prawidłowo:

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

Każda pomoc będzie być docenionym!

EDIT:

Inne przykłady to:

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

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

Ja w zasadzie starają się usunąć wszystkie z najdłuższych list, które pokrywają się z innej listy. W tym przypadku nie muszę się martwić, że listy mają taką samą długość.

Dzięki!

Answer 1

Aby usunąć minimalną liczbę interwałów z listy, tak że odstępy, które pozostały nie pokrywają się, O(n*log n) algorytm istnieje:

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 

Należy przedstawić następujące wyniki:

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

To wymaga struktura danych, która może znajdować się w O(log n + m) czasie wszystkich przedziałów, które pokrywają się z podanym przedziałem, np. IntervalTree. Istnieją implementacje, które mogą być używane z Pythona np. quicksect.py, zobacz Fast interval intersection methodologies dla przykładu użycia.

---

Oto quicksect -na O(n**2) realizacja powyższego algorytmu:

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) 

Uwaga: złożoność czas w najgorszym przypadku jest O(n**2) dla tej implementacji, ponieważ odstępy są tylko oznaczone jako usunięte np Wyobraź sobie, że takie wejście intervals, że i byłyby interwały len(intervals)/2, które obejmują cały zakres, to tree.intersect() byłyby nazywane n/3 razy, a każde wywołanie wykonałoby x.other.removed = True co najmniej n/2 razy tzn n*n/6 operacje w sumie:

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

---

Oto banyan -na O(n log n) realizacja:

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 

Uwaga: ta implementacja uważa [0, 10] i [10, 20] odstępach czasu nakładających:

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 i tree mogą być łączone:

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. sortowanie rosnące według wszystkich elementów według długości.

2. dodać je do drzewa segmentu i zignorować nałożone na siebie elementy.

Answer 3

Myślę, że jednym z problemów w twoim kodzie jest to, że nie radzi sobie z sytuacją, w której jedna lista zawiera drugą. Na przykład [0,100] zawiera [9,10]. Kiedy pętla n w [0,100] i n wchodzi [9,10], wywoływana jest instrukcja warunku if n in range(x[i+1][0], x[i+1][1]). Następnie wbudowana funkcja max będzie porównywać [0, 100] i [9, 10] i niestety max zwróci [9,10], ponieważ porównuje pierwszy numer na liście. W ten sposób usuwasz niewłaściwy element.

Próbuję innym sposobem osiągnięcia pożądanego efektu. Zamiast manipulować samą listą, tworzę nową listę. Warunkowo dołączając do niego nowy element, jeśli spełnia nasze wymagania.

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

Ogólnie dwa przedziały zachodzą gdy:

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

Jeśli tak jest w przypadku, związek z tych przedziałów jest:

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

Podobnie, przecięcie tych przedziałów będzie:

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

Answer 5

To nie może być najszybszym rozwiązaniem, ale bardzo gadatliwy i jasne - myślę.

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