Restar dos listas en Python

En Python, ¿cómo se pueden restar dos listas no únicas y desordenadas? Digamos que tenemos a = [0,1,2,1,0] y b = [0, 1, 1] Me gustaría hacer algo como c = a - b y tener c be [2, 0] o [0, 2] orden no me importa. Esto debería lanzar una excepción si a no contiene todos los elementos en b.

Tenga en cuenta que esto es diferente de los conjuntos! No estoy interesado en encontrar la diferencia de los conjuntos de elementos en a y b, estoy interesado en la diferencia entre las colecciones reales de elementos en ay b.

Puedo hacer esto con un bucle for, buscando el primer elemento de b en a y luego eliminando el elemento de b y de a, etc. Pero esto no me atrae, sería muy ineficiente (orden de O(n^2) tiempo) mientras que no debería haber ningún problema para hacer esto en tiempo O(n log n) .

Python 2.7 y 3.2 agregarán las colecciones. Clase de encuentro que es un diccionario que asigna elementos al número de apariciones del elemento. Esto puede ser usado como un multiset.

De acuerdo con los documentos, debería poder hacer algo como esto (sin probar, ya que no tengo ninguna de las versiones instaladas).

 from collections import Counter a = Counter(0,1,2,1) b = Counter(0,1,1) print a - b # ignores items in b missing in a # check every element in a is in b # a[key] returns 0 if key not in a, instead of raising an exception assert all(a[key] > b[key] for key in b) 

Editar :

Ya que estás atascado con 2.5, puedes intentar importarlo y definir tu propia versión si eso falla. De esa manera, se asegurará de obtener la última versión si está disponible y, si no, volverá a una versión funcional. También se beneficiará de las mejoras de velocidad si se convierte a una implementación de C en el futuro.

es decir

 try: from collections import Counter except ImportError: class Counter(dict): ... 

Puedes encontrar la fuente actual de Python aquí .

Sé que “para” no es lo que quieres, pero es simple y claro:

 for x in b: a.remove(x) 

O si los miembros de b podrían no estar en a entonces use:

 for x in b: if x in a: a.remove(x) 

Lo haría de una manera más fácil:

 a_b = [e for e in a if not e in b ] 

..así que escribí, esto es incorrecto – solo funciona si los elementos son únicos en las listas. Y si lo son, es mejor usarlos.

 a_b = list(set(a) - set(b)) 

No estoy seguro de cuál es la objeción a un bucle for: no hay multiset en Python, por lo que no puedes usar un contenedor incorporado para ayudarte.

Me parece que cualquier cosa en una línea (si es posible) probablemente será muy compleja de entender. Ir para la legibilidad y KISS. Python no es C 🙂

Python 2.7+ y 3.0 tienen colecciones. Contador (también conocido como multiset). La documentación enlaza con la receta 576611: Clase de contador para Python 2.5:

 from operator import itemgetter from heapq import nlargest from itertools import repeat, ifilter class Counter(dict): '''Dict subclass for counting hashable objects. Sometimes called a bag or multiset. Elements are stored as dictionary keys and their counts are stored as dictionary values. >>> Counter('zyzygy') Counter({'y': 3, 'z': 2, 'g': 1}) ''' def __init__(self, iterable=None, **kwds): '''Create a new, empty Counter object. And if given, count elements from an input iterable. Or, initialize the count from another mapping of elements to their counts. >>> c = Counter() # a new, empty counter >>> c = Counter('gallahad') # a new counter from an iterable >>> c = Counter({'a': 4, 'b': 2}) # a new counter from a mapping >>> c = Counter(a=4, b=2) # a new counter from keyword args ''' self.update(iterable, **kwds) def __missing__(self, key): return 0 def most_common(self, n=None): '''List the n most common elements and their counts from the most common to the least. If n is None, then list all element counts. >>> Counter('abracadabra').most_common(3) [('a', 5), ('r', 2), ('b', 2)] ''' if n is None: return sorted(self.iteritems(), key=itemgetter(1), reverse=True) return nlargest(n, self.iteritems(), key=itemgetter(1)) def elements(self): '''Iterator over elements repeating each as many times as its count. >>> c = Counter('ABCABC') >>> sorted(c.elements()) ['A', 'A', 'B', 'B', 'C', 'C'] If an element's count has been set to zero or is a negative number, elements() will ignore it. ''' for elem, count in self.iteritems(): for _ in repeat(None, count): yield elem # Override dict methods where the meaning changes for Counter objects. @classmethod def fromkeys(cls, iterable, v=None): raise NotImplementedError( 'Counter.fromkeys() is undefined. Use Counter(iterable) instead.') def update(self, iterable=None, **kwds): '''Like dict.update() but add counts instead of replacing them. Source can be an iterable, a dictionary, or another Counter instance. >>> c = Counter('which') >>> c.update('witch') # add elements from another iterable >>> d = Counter('watch') >>> c.update(d) # add elements from another counter >>> c['h'] # four 'h' in which, witch, and watch 4 ''' if iterable is not None: if hasattr(iterable, 'iteritems'): if self: self_get = self.get for elem, count in iterable.iteritems(): self[elem] = self_get(elem, 0) + count else: dict.update(self, iterable) # fast path when counter is empty else: self_get = self.get for elem in iterable: self[elem] = self_get(elem, 0) + 1 if kwds: self.update(kwds) def copy(self): 'Like dict.copy() but returns a Counter instance instead of a dict.' return Counter(self) def __delitem__(self, elem): 'Like dict.__delitem__() but does not raise KeyError for missing values.' if elem in self: dict.__delitem__(self, elem) def __repr__(self): if not self: return '%s()' % self.__class__.__name__ items = ', '.join(map('%r: %r'.__mod__, self.most_common())) return '%s({%s})' % (self.__class__.__name__, items) # Multiset-style mathematical operations discussed in: # Knuth TAOCP Volume II section 4.6.3 exercise 19 # and at http://en.wikipedia.org/wiki/Multiset # # Outputs guaranteed to only include positive counts. # # To strip negative and zero counts, add-in an empty counter: # c += Counter() def __add__(self, other): '''Add counts from two counters. >>> Counter('abbb') + Counter('bcc') Counter({'b': 4, 'c': 2, 'a': 1}) ''' if not isinstance(other, Counter): return NotImplemented result = Counter() for elem in set(self) | set(other): newcount = self[elem] + other[elem] if newcount > 0: result[elem] = newcount return result def __sub__(self, other): ''' Subtract count, but keep only results with positive counts. >>> Counter('abbbc') - Counter('bccd') Counter({'b': 2, 'a': 1}) ''' if not isinstance(other, Counter): return NotImplemented result = Counter() for elem in set(self) | set(other): newcount = self[elem] - other[elem] if newcount > 0: result[elem] = newcount return result def __or__(self, other): '''Union is the maximum of value in either of the input counters. >>> Counter('abbb') | Counter('bcc') Counter({'b': 3, 'c': 2, 'a': 1}) ''' if not isinstance(other, Counter): return NotImplemented _max = max result = Counter() for elem in set(self) | set(other): newcount = _max(self[elem], other[elem]) if newcount > 0: result[elem] = newcount return result def __and__(self, other): ''' Intersection is the minimum of corresponding counts. >>> Counter('abbb') & Counter('bcc') Counter({'b': 1}) ''' if not isinstance(other, Counter): return NotImplemented _min = min result = Counter() if len(self) < len(other): self, other = other, self for elem in ifilter(self.__contains__, other): newcount = _min(self[elem], other[elem]) if newcount > 0: result[elem] = newcount return result if __name__ == '__main__': import doctest print doctest.testmod() 

Entonces puedes escribir

  a = Counter([0,1,2,1,0]) b = Counter([0, 1, 1]) c = a - b print list(c.elements()) # [0, 2] 

utilizar la lista de comprensión:

 [i for i in a if not i in b or b.remove(i)] 

Haría el truco. Sin embargo, cambiaría b en el proceso. Pero estoy de acuerdo con jkp y Dyno Fu en que usar un bucle for sería mejor.

Tal vez alguien pueda crear un ejemplo mejor que use la comprensión de listas pero aún así sea KISS.

Para probar el punto de JKP de que “cualquier cosa en una línea probablemente será muy compleja de entender”, creé una frase de una sola línea. Por favor, no me modesten porque entiendo que esta no es una solución que realmente deba usar. Es sólo para fines demostrativos.

La idea es agregar los valores uno por uno, siempre y cuando el total de veces que haya agregado el valor sea menor que el número total de veces que este valor esté en a menos el número de veces que esté en b:

 [ value for counter,value in enumerate(a) if a.count(value) >= b.count(value) + a[counter:].count(value) ] 

¡El horror! Pero tal vez alguien pueda mejorarlo? ¿Es incluso libre de errores?

Edit: Al ver el comentario de Devin Jeanpierre sobre el uso de una estructura de datos del diccionario, se me ocurrió este oneliner:

 sum([ [value]*count for value,count in {value:a.count(value)-b.count(value) for value in set(a)}.items() ], []) 

Mejor, pero aún ilegible.

Puedes probar algo como esto:

 class mylist(list): def __sub__(self, b): result = self[:] b = b[:] while b: try: result.remove(b.pop()) except ValueError: raise Exception("Not all elements found during subtraction") return result a = mylist([0, 1, 2, 1, 0] ) b = mylist([0, 1, 1]) >>> a - b [2, 0] 

Sin embargo, debe definir qué [1, 2, 3] – [5, 6] debe emitir, supongo que desea [1, 2, 3] por eso ignoro el ValueError.

Edición: Ahora veo que quería una excepción si a no contiene todos los elementos, se agregó en lugar de pasar el ValueError.

Intenté encontrar una solución más elegante, pero lo mejor que pude hacer fue básicamente lo mismo que dijo Dyno Fu:

 from copy import copy def subtract_lists(a, b): """ >>> a = [0, 1, 2, 1, 0] >>> b = [0, 1, 1] >>> subtract_lists(a, b) [2, 0] >>> import random >>> size = 10000 >>> a = [random.randrange(100) for _ in range(size)] >>> b = [random.randrange(100) for _ in range(size)] >>> c = subtract_lists(a, b) >>> assert all((x in a) for x in c) """ a = copy(a) for x in b: if x in a: a.remove(x) return a 

Aquí hay una solución relativamente larga pero eficiente y legible. Esta encendido).

 def list_diff(list1, list2): counts = {} for x in list1: try: counts[x] += 1 except: counts[x] = 1 for x in list2: try: counts[x] -= 1 if counts[x] < 0: raise ValueError('All elements of list2 not in list2') except: raise ValueError('All elements of list2 not in list1') result = [] for k, v in counts.iteritems(): result += v*[k] return result a = [0, 1, 1, 2, 0] b = [0, 1, 1] %timeit list_diff(a, b) %timeit list_diff(1000*a, 1000*b) %timeit list_diff(1000000*a, 1000000*b) 100000 loops, best of 3: 4.8 µs per loop 1000 loops, best of 3: 1.18 ms per loop 1 loops, best of 3: 1.21 s per loop 

Puedes usar la construcción del map para hacer esto. Se ve bastante bien, pero ten en cuenta que la línea del map sí devolverá una lista de None .

 a = [1, 2, 3] b = [2, 3] map(lambda x:a.remove(x), b) a 
 c = [i for i in b if i not in a] 
 list(set([x for x in a if x not in b])) 
  • Deja b sin tocar.
  • Es un conjunto único de “a – b”.
  • Hecho.