Filtrado de listas de Python: eliminar subconjuntos de la lista de listas

Usando Python, ¿cómo reduce una lista de listas por un subconjunto ordenado de concordancia [[..],[..],..] ?

En el contexto de esta pregunta, una lista L es un subconjunto de la lista M si M contiene todos los miembros de L , y en el mismo orden. Por ejemplo, la lista [1,2] es un subconjunto de la lista [1,2,3], pero no de la lista [2,1,3].

Ejemplo de entrada:

 a. [[1, 2, 4, 8], [1, 2, 4, 5, 6], [1, 2, 3], [2, 3, 21], [1, 2, 3, 4], [1, 2, 3, 4, 5, 6, 7]] b. [[2, 16, 17], [1, 2, 3, 4, 5, 6, 7], [1], [1, 2, 3, 4], [1, 2], [17, 18, 19, 22, 41, 48], [2, 3], [1, 2, 3], [50, 69], [1, 2, 3], [2, 3, 21], [1, 2, 3], [1, 2, 4, 8], [1, 2, 4, 5, 6]] 

Resultado Esperado:

 a. [[1, 2, 4, 8], [2, 3, 21], [1, 2, 3, 4, 5, 6, 7]] b. [[2, 16, 17], [1, 2, 3, 4, 5, 6, 7], [17, 18, 19, 22, 41, 48], [50, 69], [2, 3, 21], [1, 2, 4, 8], [1, 2, 4, 5, 6]] 

Otros ejemplos:

L = [[1, 2, 3, 4, 5, 6, 7], [1, 2, 5, 6]] – Sin reducción

L = [[1, 2, 3, 4, 5, 6, 7], [1, 2, 3] , [1, 2, 4, 8]] – Sí reducir

L = [[1, 2, 3, 4, 5, 6, 7], [7, 6, 5, 4, 3, 2, 1]] – Sin reducción

(Lo siento por causar confusión con el conjunto de datos incorrecto.)

Esto podría ser simplificado, pero:

 l = [[1, 2, 4, 8], [1, 2, 4, 5, 6], [1, 2, 3], [2, 3, 21], [1, 2, 3, 4], [1, 2, 3, 4, 5, 6, 7]] l2 = l[:] for m in l: for n in l: if set(m).issubset(set(n)) and m != n: l2.remove(m) break print l2 [[1, 2, 4, 8], [2, 3, 21], [1, 2, 3, 4, 5, 6, 7]] 

Este código debería ser bastante eficiente en memoria. Más allá de almacenar su lista inicial de listas, este código utiliza una memoria extra despreciable (no se crean conjuntos o copias temporales de listas).

 def is_subset(needle,haystack): """ Check if needle is ordered subset of haystack in O(n) """ if len(haystack) < len(needle): return False index = 0 for element in needle: try: index = haystack.index(element, index) + 1 except ValueError: return False else: return True def filter_subsets(lists): """ Given list of lists, return new list of lists without subsets """ for needle in lists: if not any(is_subset(needle, haystack) for haystack in lists if needle is not haystack): yield needle my_lists = [[1, 2, 4, 8], [1, 2, 4, 5, 6], [1, 2, 3], [2, 3, 21], [1, 2, 3, 4], [1, 2, 3, 4, 5, 6, 7]] print list(filter_subsets(my_lists)) >>> [[1, 2, 4, 8], [2, 3, 21], [1, 2, 3, 4, 5, 6, 7]] 

Y, sólo por diversión, una sola línea:

 def filter_list(L): return [x for x in L if not any(set(x)<=set(y) for y in L if x is not y)] 

Una lista es una súper lista si no es un subconjunto de cualquier otra lista. Es un subconjunto de otra lista si cada elemento de la lista se puede encontrar, en orden, en otra lista.

Aquí está mi código:

 def is_sublist_of_any_list(cand, lists): # Compare candidate to a single list def is_sublist_of_list(cand, target): try: i = 0 for c in cand: i = 1 + target.index(c, i) return True except ValueError: return False # See if candidate matches any other list return any(is_sublist_of_list(cand, target) for target in lists if len(cand) <= len(target)) # Compare candidates to all other lists def super_lists(lists): return [cand for i, cand in enumerate(lists) if not is_sublist_of_any_list(cand, lists[:i] + lists[i+1:])] if __name__ == '__main__': lists = [[1, 2, 4, 8], [1, 2, 4, 5, 6], [1, 2, 3], [2, 3, 21], [1, 2, 3, 4], [1, 2, 3, 4, 5, 6, 7]] superlists = super_lists(lists) print superlists 

Aquí están los resultados:

 [[1, 2, 4, 8], [2, 3, 21], [1, 2, 3, 4, 5, 6, 7]] 

Editar: Resultados para su posterior conjunto de datos.

 >>> lists = [[2, 16, 17], [1, 2, 3, 4, 5, 6, 7], [1], [1, 2, 3, 4], [1, 2], [17, 18, 19, 22, 41, 48], [2, 3], [1, 2, 3], [50, 69], [1, 2, 3], [2, 3, 21], [1, 2, 3], [1, 2, 4, 8], [1, 2, 4, 5, 6]] >>> superlists = super_lists(lists) >>> expected = [[2, 16, 17], [1, 2, 3, 4, 5, 6, 7], [17, 18, 19, 22, 41, 48], [5 0, 69], [2, 3, 21], [1, 2, 4, 8]] >>> assert(superlists == expected) >>> print superlists [[2, 16, 17], [1, 2, 3, 4, 5, 6, 7], [17, 18, 19, 22, 41, 48], [50, 69], [2, 3, 21], [1, 2, 4, 8]] 

Esto parece funcionar:

 original=[[1, 2, 4, 8], [1, 2, 4, 5, 6], [1, 2, 3], [2, 3, 21], [1, 2, 3, 4], [1, 2, 3, 4, 5, 6, 7]] target=[[1, 2, 4, 8], [2, 3, 21], [1, 2, 3, 4, 5, 6, 7]] class SetAndList: def __init__(self,aList): self.list=aList self.set=set(aList) self.isUnique=True def compare(self,aList): s=set(aList) if self.set.issubset(s): #print self.list,'superceded by',aList self.isUnique=False def listReduce(lists): temp=[] for l in lists: for t in temp: t.compare(l) temp.append( SetAndList(l) ) return [t.list for t in temp if t.isUnique] print listReduce(original) print target 

Esto imprime la lista calculada y el objective para la comparación visual.

Descomente la línea de impresión en el método de comparación para ver cómo se eliminan varias listas.

Probado con python 2.6.2

Implementé un issubseq diferente porque el tuyo no dice que [1, 2, 4, 5, 6] es una subsecuencia de [1, 2, 3, 4, 5, 6, 7] , por ejemplo (además de ser dolorosamente lento ). La solución que se me ocurrió se ve así:

  def is_subseq(a, b): if len(a) > len(b): return False start = 0 for el in a: while start < len(b): if el == b[start]: break start = start + 1 else: return False return True def filter_partial_matches(sets): return [s for s in sets if all([not(is_subseq(s, ss)) for ss in sets if s != ss])] 

Un caso de prueba simple, dadas sus entradas y salidas:

 >>> test = [[1, 2, 4, 8], [1, 2, 4, 5, 6], [1, 2, 3], [2, 3, 21], [1, 2, 3, 4], [1, 2, 3, 4, 5, 6, 7]] >>> another_test = [[1, 2, 3, 4], [2, 4, 3], [3, 4, 5]] >>> filter_partial_matches(test) [[1, 2, 4, 8], [2, 3, 21], [1, 2, 3, 4, 5, 6, 7]] >>> filter_partial_matches(another_test) [[1, 2, 3, 4], [2, 4, 3], [3, 4, 5]] 

¡Espero eso ayude!

 list0=[[1, 2, 4, 8], [1, 2, 4, 5, 6], [1, 2, 3], [2, 3, 21], [1, 2, 3, 4], [1, 2, 3, 4, 5, 6, 7]] for list1 in list0[:]: for list2 in list0: if list2!=list1: len1=len(list1) c=0 for n in list2: if n==list1[c]: c+=1 if c==len1: list0.remove(list1) break 

Esto filtra la lista en su lugar usando una copia de ella. Esto es bueno si se espera que el resultado sea aproximadamente del mismo tamaño que el original, solo hay unos pocos “subconjuntos” para eliminar.

Si se espera que el resultado sea pequeño y el original sea grande, es posible que prefiera este que tenga más memoria con facilidad ya que no copia la lista original.

 list0=[[1, 2, 4, 8], [1, 2, 4, 5, 6], [1, 2, 3], [2, 3, 21], [1, 2, 3, 4], [1, 2, 3, 4, 5, 6, 7]] result=[] for list1 in list0: subset=False for list2 in list0: if list2!=list1: len1=len(list1) c=0 for n in list2: if n==list1[c]: c+=1 if c==len1: subset=True break if subset: break if not subset: result.append(list1) 

Edit: Realmente necesito mejorar mi comprensión de lectura. Aquí está la respuesta a lo que realmente se preguntó. Explota el hecho de que ” A is super of B ” implica ” len(A) > len(B) or A == B “.

 def advance_to(it, value): """Advances an iterator until it matches the given value. Returns False if not found.""" for item in it: if item == value: return True return False def has_supersequence(seq, super_sequences): """Checks if the given sequence has a supersequence in the list of supersequences.""" candidates = map(iter, super_sequences) for next_item in seq: candidates = [seq for seq in candidates if advance_to(seq, next_item)] return len(candidates) > 0 def find_supersequences(sequences): """Finds the supersequences in the given list of sequences. Sequence A is a supersequence of sequence B if B can be created by removing items from A.""" super_seqs = [] for candidate in sorted(sequences, key=len, reverse=True): if not has_supersequence(candidate, super_seqs): super_seqs.append(candidate) return super_seqs print(find_supersequences([[1, 2, 4, 8], [1, 2, 4, 5, 6], [1, 2, 3], [2, 3, 21], [1, 2, 3, 4], [1, 2, 3, 4, 5, 6, 7]])) #Output: [[1, 2, 3, 4, 5, 6, 7], [1, 2, 4, 8], [2, 3, 21]] 

Si también necesita conservar el orden original de las secuencias, la función find_supersequences() debe realizar un seguimiento de las posiciones de las secuencias y ordenar la salida posteriormente.

Respuesta refinada después de un nuevo caso de prueba:

 original= [[2, 16, 17], [1, 2, 3, 4, 5, 6, 7], [1], [1, 2, 3, 4], [1, 2], [17, 18, 19, 22, 41, 48], [2, 3], [1, 2, 3], [50, 69], [1, 2, 3], [2, 3, 21], [1, 2, 3], [1, 2, 4, 8], [1, 2, 4, 5, 6]] class SetAndList: def __init__(self,aList): self.list=aList self.set=set(aList) self.isUnique=True def compare(self,other): if self.set.issubset(other.set): #print self.list,'superceded by',other.list self.isUnique=False def listReduce(lists): temp=[] for l in lists: s=SetAndList(l) for t in temp: t.compare(s) s.compare(t) temp.append( s ) temp=[t for t in temp if t.isUnique] return [t.list for t in temp if t.isUnique] print listReduce(original) 

No dio la salida requerida, pero supongo que esto es correcto, ya que [1,2,3] no aparece en la salida.

Gracias a todos los que sugirieron soluciones y lidiar con mis conjuntos de datos a veces erróneos. Usando la solución @hughdbrown , la modifiqué a lo que quería:

La modificación consistió en utilizar una ventana deslizante sobre el objective para garantizar que se encontró la secuencia del subconjunto. Creo que debería haber usado una palabra más apropiada que “Establecer” para describir mi problema.

 def is_sublist_of_any_list(cand, lists): # Compare candidate to a single list def is_sublist_of_list(cand, target): try: i = 0 try: start = target.index(cand[0]) except: return False while start < (len(target) + len(cand)) - start: if cand == target[start:len(cand)]: return True else: start = target.index(cand[0], start + 1) except ValueError: return False # See if candidate matches any other list return any(is_sublist_of_list(cand, target) for target in lists if len(cand) <= len(target)) # Compare candidates to all other lists def super_lists(lists): a = [cand for i, cand in enumerate(lists) if not is_sublist_of_any_list(cand, lists[:i] + lists[i+1:])] return a lists = [[2, 16, 17], [1, 2, 3, 4, 5, 6, 7], [1], [1, 2, 3, 4], [1, 2], [17, 18, 19, 22, 41, 48], [2, 3], [1, 2, 3], [50, 69], [1, 2, 3], [2, 3, 21], [1, 2, 3], [1, 2, 4, 8], [1, 2, 4, 5, 6]] expect = [[2, 16, 17], [1, 2, 3, 4, 5, 6, 7], [17, 18, 19, 22, 41, 48], [50, 69], [2, 3, 21], [1, 2, 4, 8], [1, 2, 4, 5, 6]] def test(): out = super_lists(list(lists)) print "In : ", lists print "Out : ", out assert (out == expect) 

Resultado:

 In : [[2, 16, 17], [1, 2, 3, 4, 5, 6, 7], [1], [1, 2, 3, 4], [1, 2], [17, 18, 19, 22, 41, 48], [2, 3], [1, 2, 3], [50, 69], [1, 2, 3], [2, 3, 21], [1, 2, 3], [1, 2, 4, 8], [1, 2, 4, 5, 6]] Out : [[2, 16, 17], [1, 2, 3, 4, 5, 6, 7], [17, 18, 19, 22, 41, 48], [50, 69], [2, 3, 21], [1, 2, 4, 8], [1, 2, 4, 5, 6]] 

Entonces, lo que realmente quería era saber si una lista era una subcadena, por así decirlo, de otra, con todos los elementos coincidentes consecutivos. Aquí está el código que convierte el candidato y la lista de destino en cadenas separadas por comas y hace una comparación de subcadena para ver si el candidato aparece dentro de la lista de destino

 def is_sublist_of_any_list(cand, lists): def comma_list(l): return "," + ",".join(str(x) for x in l) + "," cand = comma_list(cand) return any(cand in comma_list(target) for target in lists if len(cand) <= len(target)) def super_lists(lists): return [cand for i, cand in enumerate(lists) if not is_sublist_of_any_list(cand, lists[:i] + lists[i+1:])] 

La función comma_list () coloca comas iniciales y finales en la lista para asegurar que los enteros estén completamente delimitados. De lo contrario, [1] sería un subconjunto de [100], por ejemplo.