¿La mejor manera de encontrar la intersección de múltiples conjuntos?

267

Tengo una lista de conjuntos:

setlist = [s1,s2,s3...]

Quiero s1 ∩ s2 ∩ s3 ...

Puedo escribir una función para hacerlo realizando una serie de pares s1.intersection(s2), etc.

¿Existe una forma recomendada, mejor o incorporada?

usuario116293
fuente

Respuestas:

454

Desde Python versión 2.6 en adelante puedes usar múltiples argumentos para set.intersection(), como

u = set.intersection(s1, s2, s3)

Si los conjuntos están en una lista, esto se traduce en:

u = set.intersection(*setlist)

¿Dónde *a_listestá la expansión de la lista?

Tenga en cuenta que noset.intersection es un método estático, pero utiliza la notación funcional para aplicar la intersección del primer conjunto con el resto de la lista. Entonces, si la lista de argumentos está vacía, esto fallará.

algo
fuente
65

A partir de 2.6, set.intersectiontoma arbitrariamente muchos iterables.

>>> s1 = set([1, 2, 3])
>>> s2 = set([2, 3, 4])
>>> s3 = set([2, 4, 6])
>>> s1 & s2 & s3
set([2])
>>> s1.intersection(s2, s3)
set([2])
>>> sets = [s1, s2, s3]
>>> set.intersection(*sets)
set([2])
Mike Graham
fuente
24

Claramente set.intersectiones lo que quiere aquí, pero en caso de que necesite una generalización de "tomar la suma de todos estos", "tomar el producto de todos estos", "tomar el xor de todos estos", lo que está buscando es el reducefunción:

from operator import and_
from functools import reduce
print(reduce(and_, [{1,2,3},{2,3,4},{3,4,5}])) # = {3}

o

print(reduce((lambda x,y: x&y), [{1,2,3},{2,3,4},{3,4,5}])) # = {3}
Thomas Ahle
fuente
12

Si no tiene Python 2.6 o superior, la alternativa es escribir un bucle for explícito:

def set_list_intersection(set_list):
  if not set_list:
    return set()
  result = set_list[0]
  for s in set_list[1:]:
    result &= s
  return result

set_list = [set([1, 2]), set([1, 3]), set([1, 4])]
print set_list_intersection(set_list)
# Output: set([1])

También puedes usar reduce:

set_list = [set([1, 2]), set([1, 3]), set([1, 4])]
print reduce(lambda s1, s2: s1 & s2, set_list)
# Output: set([1])

Sin embargo, a muchos programadores de Python no les gusta, incluido el propio Guido :

Hace unos 12 años, Python adquirió lambda, reduce (), filter () y map (), cortesía de (creo) un pirata informático de Lisp que los perdió y envió parches de trabajo. Pero, a pesar del valor de PR, creo que estas características deberían cortarse de Python 3000.

Entonces ahora reduce (). Este es en realidad el que siempre he odiado más, porque, aparte de algunos ejemplos que involucran + o *, casi cada vez que veo una llamada reduce () con un argumento de función no trivial, necesito tomar lápiz y papel para Diagrama de lo que realmente se está alimentando en esa función antes de que entienda lo que se supone que debe hacer reduce (). Entonces, en mi opinión, la aplicabilidad de reduce () está bastante limitada a operadores asociativos, y en todos los demás casos es mejor escribir explícitamente el ciclo de acumulación.

Ayman Hourieh
fuente
8
Tenga en cuenta que Guido dice que el uso reduceestá "limitado a operadores asociativos", lo cual es aplicable en este caso. reduceA menudo es difícil de entender, pero &no es tan malo.
Mike Graham
Echa un vistazo a python.org/doc/essays/list2str para obtener optimizaciones útiles relacionadas con la reducción. En general, se puede usar bastante bien para crear listas, conjuntos, cadenas, etc. También vale la pena echarle un vistazo a github.com/EntilZha/PyFunctional
Andreas
Tenga en cuenta que puede optimizar interrumpiendo su ciclo cuando resultestá vacío.
bfontaine
1

Aquí estoy ofreciendo una función genérica para la intersección de conjuntos múltiples tratando de aprovechar el mejor método disponible:

def multiple_set_intersection(*sets):
    """Return multiple set intersection."""
    try:
        return set.intersection(*sets)
    except TypeError: # this is Python < 2.6 or no arguments
        pass

    try: a_set= sets[0]
    except IndexError: # no arguments
        return set() # return empty set

    return reduce(a_set.intersection, sets[1:])

Puede que a Guido no le guste reduce, pero me gusta mucho :)

tzot
fuente
Debe verificar la longitud de en setslugar de intentar acceder sets[0]y capturar el IndexError.
bfontaine
Esto no es un simple cheque; a_setse usa en el retorno final.
tzot
¿No puedes hacer return reduce(sets[0], sets[1:]) if sets else set()?
bfontaine
Ja si, gracias. El código debería cambiar porque si se puede evitar depender de un try/ except. Es un olor a código, es ineficiente y puede ocultar otros problemas.
bfontaine
0

La respuesta de Jean-François Fabre set.intesection (* list_of_sets) es definitivamente la más Pyhtonic y es la respuesta aceptada.

Para aquellos que quieran usar reducir, lo siguiente también funcionará:

reduce(set.intersection, list_of_sets)

Minas
fuente