encontrar la “superposición” entre 2 listas de python

Dadas 2 listas:

a = [3,4,5,5,5,6] b = [1,3,4,4,5,5,6,7] 

Quiero encontrar la “superposición”:

 c = [3,4,5,5,6] 

También me gustaría si pudiera extraer el “rest” de la parte de a y b que no está en c.

 a_remainder = [5,] b_remainder = [1,4,7,] 

Nota: a tiene tres 5 en él y b tiene dos. b tiene dos 4 en él y a tiene uno.

La lista resultante c debe tener dos 5 (limitada por la lista b) y una 4 (limitada por la lista a).

Esto me da lo que quiero, pero no puedo evitar pensar que hay una manera mucho mejor.

 import copy a = [3,4,5,5,5,6] b = [1,3,4,4,5,5,6,7] c = [] for elem in copy.deepcopy(a): if elem in b: a.pop(a.index(elem)) c.append(b.pop(b.index(elem))) # now a and b both contain the "remainders" and c contains the "overlap" 

En otra nota, ¿cuál es un nombre más preciso para lo que estoy pidiendo que “superposición” y “rest”?

collection.Counter disponible en Python 2.7 se puede usar para implementar multisets que hacen exactamente lo que quieres.

 a = [3,4,5,5,5,6] b = [1,3,4,4,5,5,6,7] a_multiset = collections.Counter(a) b_multiset = collections.Counter(b) overlap = list((a_multiset & b_multiset).elements()) a_remainder = list((a_multiset - b_multiset).elements()) b_remainder = list((b_multiset - a_multiset).elements()) print overlap, a_remainder, b_remainder 

En el lenguaje de los conjuntos, la superposición es “intersección” y el rest es “diferencia establecida”. Si tuviera elementos distintos, no tendría que hacer estas operaciones usted mismo, visite http://docs.python.org/library/sets.html si está interesado.

Ya que no estamos trabajando con elementos distintos, su enfoque es razonable. Si desea que esto se ejecute más rápido, puede crear un diccionario para cada lista y asignar el número a cuántos elementos hay en cada matriz (por ejemplo, en a, 3-> 1, 4-> 1, 5-> 2, etc. .). Luego, debe iterar en el mapa a, determinar si esa letra existió, disminuir su conteo y agregarla a la nueva lista

Código no probado, pero esta es la idea.

 def add_or_update(map,value): if value in map: map[value]+=1 else map[value]=1 b_dict = dict() for b_elem in b: add_or_update(b_dict,b_elem) intersect = []; diff = []; for a_elem in a: if a_elem in b_dict and b_dict[a_elem]>0: intersect.add(a_elem); for k,v in diff: for i in range(v): diff.add(k); 

Utilizar conjunto de python

 intersection = set(a) & set(b) a_remainder = set(a) - set(b) b_remainder = set(b) - set(a) 

OK, detallado, pero un poco genial (similar en espíritu a las collections.Counter Idea de encuentro, pero más casero):

 import itertools as it flatten = it.chain.from_iterable sorted( v for u,v in set(flatten(enumerate(g) for k, g in it.groupby(a))).intersection( set(flatten(enumerate(g) for k, g in it.groupby(b)))) ) 

La idea básica es convertir cada una de las listas en una nueva lista que adjunte un contador a cada objeto, numerados para tener en cuenta los duplicados, para que luego pueda utilizar las operaciones de set en estas tuplas después de todo.

Para ser un poco menos verboso:

  aa = set(flatten(enumerate(g) for k, g in it.groupby(a))) bb = set(flatten(enumerate(g) for k, g in it.groupby(b))) # aa = set([(0, 3), (0, 4), (0, 5), (0, 6), (1, 5), (2, 5)]) # bb = set([(0, 1), (0, 3), (0, 4), (0, 5), (0, 6), (0, 7), (1, 4), (1, 5)]) cc = aa.intersection(bb) # cc = set([(0, 3), (0, 4), (0, 5), (0, 6), (1, 5)]) c = sorted(v for u,v in cc) # c = [3, 4, 5, 5, 6] 
  • groupby : produce una lista de listas que contienen elementos idénticos (pero debido a la syntax necesita g for k,g in it.groupby(a) para extraer cada lista)
  • enumerate – agrega un contador a cada elemento de cada lista secundaria
  • flatten – crear una sola lista
  • set – convertir a un set
  • intersection – encontrar los elementos comunes
  • sorted(v for u,v in cc) : elimine los contadores y ordene el resultado

Por último, no estoy seguro de lo que quiere decir con los rests; Parece que debería ser mi aa-cc y bb-cc pero no sé de dónde a_remainder = [4] :

 sorted(v for u,v in aa-cc) # [5] sorted(v for u,v in bb-cc) # [1, 4, 7] 

Una respuesta de kerio en #python en freenode:

 [ i for i in itertools.chain.from_iterable([k] * v for k, v in \ (Counter(a) & Counter(b)).iteritems()) ] 

Pruebe difflib.SequenceMatcher () , “una clase flexible para comparar pares de secuencias de cualquier tipo” …

Un bash rápido:

 a = [3,4,5,5,5,6] b = [1,3,4,4,5,5,6,7] sm = difflib.SequenceMatcher(None, a, b) c = [] a_remainder = [] b_remainder = [] for tag, i1, i2, j1, j2 in sm.get_opcodes(): if tag == 'replace': a_remainder.extend(a[i1:i2]) b_remainder.extend(b[j1:j2]) elif tag == 'delete': a_remainder.extend(a[i1:i2]) elif tag == 'insert': b_remainder.extend(b[j1:j2]) elif tag == 'equal': c.extend(a[i1:i2]) 

Y ahora…

 >>> print c [3, 4, 5, 5, 6] >>> print a_remainder [5] >>> print b_remainder [1, 4, 7] 
 Aset = Set(a); Bset = Set(b); a_remainder = a.difference(b); b_remainder = b.difference(a); c = a.intersection(b); 

Pero si necesita c para tener duplicados, y el orden es importante para usted,
puede buscar w: el problema de subsecuencia común más largo

No creo que realmente debas usar esta solución, pero aproveché esta oportunidad para practicar con las funciones lambda y esto es lo que se me ocurrió 🙂

 a = [3,4,5,5,5,6] b = [1,3,4,4,5,5,6,7] dedup = lambda x: [set(x)] if len(set(x)) == len(x) else [set(x)] + dedup([x[i] for i in range(1, len(x)) if x[i] == x[i-1]]) default_set = lambda x: (set() if x[0] is None else x[0], set() if x[1] is None else x[1]) deduped = map(default_set, map(None, dedup(a), dedup(b))) get_result = lambda f: reduce(lambda x, y: list(x) + list(y), map(lambda x: f(x[0], x[1]), deduped)) c = get_result(lambda x, y: x.intersection(y)) # [3, 4, 5, 6, 5] a_remainder = get_result(lambda x, y: x.difference(y)) # [5] b_remainder = get_result(lambda x, y: y.difference(x)) # [1, 7, 4] 

Estoy bastante seguro de que izip_longest lo habría simplificado un poco (no habría necesitado el default_set lambda), pero lo estaba probando con Python 2.5.

Estos son algunos de los valores intermedios utilizados en el cálculo en caso de que alguien quiera entender esto:

 dedup(a) = [set([3, 4, 5, 6]), set([5]), set([5])] dedup(b) = [set([1, 3, 4, 5, 6, 7]), set([4, 5])] deduped = [(set([3, 4, 5, 6]), set([1, 3, 4, 5, 6, 7])), (set([5]), set([4, 5])), (set([5]), set([]))]