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([]))]