Resta sobre una lista de conjuntos

Dada una lista de conjuntos:

allsets = [set([1, 2, 4]), set([4, 5, 6]), set([4, 5, 7])] 

¿Cuál es una forma pythonica de calcular la lista correspondiente de conjuntos de elementos que no se superponen con otros conjuntos?

 only = [set([1, 2]), set([6]), set([7])] 

¿Hay alguna manera de hacer esto con una lista de comprensión?

Para evitar el tiempo de ejecución cuadrático, querría hacer un pase inicial para averiguar qué elementos aparecen en más de un conjunto:

 import itertools import collections element_counts = collections.Counter(itertools.chain.from_iterable(allsets)) 

Luego, puede simplemente hacer una lista de conjuntos que retengan todos los elementos que solo aparecen una vez:

 nondupes = [{elem for elem in original if element_counts[elem] == 1} for original in allsets] 

De manera alternativa, en lugar de construir nondupes partir de element_counts , podemos hacer un pase adicional para construir un conjunto de todos los elementos que aparecen exactamente en una entrada. Esto requiere una statement adicional, pero nos permite aprovechar el operador & para establecer la intersección para hacer que la comprensión de la lista sea más corta y más eficiente:

 element_counts = collections.Counter(itertools.chain.from_iterable(allsets)) all_uniques = {elem for elem, count in element_counts.items() if count == 1} # ^ viewitems() in Python 2.7 nondupes = [original & all_uniques for original in allsets] 

El tiempo parece indicar que el uso de un conjunto all_uniques produce una aceleración sustancial para el proceso general de eliminación de duplicados. Se trata de una aceleración de aproximadamente 3.5x en Python 3 para conjuntos de entradas fuertemente duplicados, aunque solo una aceleración de alrededor del 30% para el proceso general de eliminación de duplicados en Python 2 debido a que una mayor parte del tiempo de ejecución está dominado por la construcción del contador. Esta aceleración es bastante importante, aunque no tan importante como evitar el tiempo de ejecución cuadrático utilizando element_counts en primer lugar. Si estás en Python 2 y este código es crítico para la velocidad, querrías usar un dict ordinario o un dict lugar de un Counter .

Otra forma sería construir un conjunto de element_counts partir de element_counts y usar original - dupes lugar de original & all_uniques en la lista de comprensión, como lo sugiere munk. Si esto funciona mejor o peor que usar un conjunto all_uniques y & dependería del grado de duplicación en su entrada y de la versión de Python en la que se encuentre, pero no parece hacer una gran diferencia de ninguna manera.

Sí se puede hacer pero no es python.

 >>> [(i-set.union(*[j for j in allsets if j!= i])) for i in allsets] [set([1, 2]), set([6]), set([7])] 

Se puede encontrar alguna referencia sobre conjuntos en la documentación . El operador * se llama operador de desembalaje .

Una solución ligeramente diferente que utiliza Contador y comprensiones, para aprovechar el operador para establecer la diferencia.

 from itertools import chain from collections import Counter allsets = [{1, 2, 4}, {4, 5, 6}, {4, 5, 7}] element_counts = Counter(chain.from_iterable(allsets)) dupes = {key for key in element_counts if element_counts[key] > 1} only = [s - dupes for s in allsets] 

Otra solución con itertools.chain :

 >>> from itertools import chain >>> [x - set(chain(*(y for y in allsets if y!=x))) for x in allsets] [set([1, 2]), set([6]), set([7])] 

También se puede hacer sin el desempaquetado y el uso de chain.from_iterable en chain.from_iterable lugar.