Python – Eliminar listas superpuestas

Digamos que tengo una lista de listas que tiene índices [[start, end], [start1, end1], [start2, end2]] .

Como por ejemplo :

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

¿Cómo obtendría la verificación de la superposición entre las listas y eliminar la lista con la longitud más larga cada vez? Asi que:

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

Esto es lo que intenté hacer hasta ahora:

 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 

Pero además de ser un poco complicado, no funciona correctamente:

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

¡Cualquier ayuda sería apreciada!

EDITAR:

Otros ejemplos serían:

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

Básicamente estoy tratando de eliminar todas las listas más largas que se superponen con otra lista. En este caso, no tengo que preocuparme de que las listas tengan la misma longitud.

¡¡Gracias!!

Para eliminar un número mínimo de intervalos de la lista, de modo que los intervalos que quedan no se superpongan, existe el algoritmo 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 

Debe producir los siguientes resultados:

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

Requiere la estructura de datos que puede encontrar en O(log n + m) tiempo todos los intervalos que se superponen con el intervalo dado, por ejemplo, IntervalTree . Existen implementaciones que se pueden usar desde Python, por ejemplo, quicksect.py , consulte Metodologías de intersección de intervalo rápido para el uso de ejemplo.


Aquí hay una quicksect O(n**2) basada en quicksect del algoritmo anterior:

 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) 

Nota: la complejidad del tiempo en el peor de los casos es O(n**2) para esta implementación porque los intervalos solo se marcan como eliminados, por ejemplo, imagine tales intervals entrada que len(result) == len(intervals) / 3 y hubo len(intervals) / 2 intervalos que abarcan todo el rango y luego tree.intersect() se tree.intersect() n/3 veces y cada llamada ejecutará x.other.removed = True al menos n/2 veces, es decir, n*n/6 Operaciones en total:

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

Aquí hay una implementación de O(n log n) basada en 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 

Nota: esta implementación considera que los intervalos [0, 10] y [10, 20] se superponen:

 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 y el tree se pueden combinar:

 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 

Puede que esta no sea la solución más rápida, pero realmente detallada y clara, creo.

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

Creo que un problema en su código es que no se maneja con la situación donde una lista contiene otra. Por ejemplo, [0,100] contiene [9,10] . Cuando realiza un bucle n en [0,100] y n ingresa [9,10], la statement de condición if n in range(x[i+1][0], x[i+1][1]) se activa. Luego, la función incorporada max comparará [0, 100] y [9, 10] , y desafortunadamente max devolverá [9,10] porque compara el primer número en la lista. Así eliminas el elemento equivocado.

Estoy intentando otra forma de lograr el efecto que quieres. En lugar de manipular la lista en sí, creo una nueva lista. Condicionalmente le agregamos un nuevo elemento si cumple con nuestros requisitos.

 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[1]: to_insert = False if to_insert: ranges.append(l) return ranges 
  1. Ascendente ordenar todos los elementos por longitud.

  2. agréguelos a un árbol de segmentos e ignore los elementos superpuestos.

En general, dos intervalos se superponen si:

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

Si este es el caso, la unión de esos intervalos es:

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

Del mismo modo, la intersección de esos intervalos será:

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