La mejor manera de encontrar la intersección de varios conjuntos?

Question

Tengo una lista de conjuntos:

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

Quiero s1 s2 ∩ ∩ s3 ...

Me puede escribir una función para hacerlo mediante la realización de una serie de s1.intersection(s2) por parejas, etc.

¿Hay un recomendado, mejor, o incorporado en forma?

Answer 1

A partir de la versión 2.6 de Python en la que puede utilizar varios argumentos a 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)

donde *a_list es

Answer 2

A partir de 2.6, set.intersection toma 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])

Answer 3

Es evidente que set.intersection es lo que usted 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 ellos", lo que eres buscando es la función reduce:

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}

Answer 4

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

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 puede utilizar 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, muchos programadores de Python no les gusta, incluido el propio Guido :

  

Hace aproximadamente 12 años, Python adquirió lambda, reducir (), filter () y el mapa (), cortesía de (creo) un hacker Lisp que los echaba de menos y presentó parches de trabajo. Pero, a pesar del valor de la banda, creo que estas características deben ser cortados de Python 3000.

     

Así que ahora reducir (). Esto es en realidad la que siempre he odiado la mayoría, ya que, aparte de unos pocos ejemplos que involucran + o *, casi cada vez que veo una llamada reducir () con un argumento de función no trivial, tengo que agarrar la pluma y papel para diagrama de lo que realmente está siendo alimentado en esa función antes de que entienda lo que el reducir () se supone que debe hacer. Así que en mi mente, la aplicabilidad de reducir () es más o menos limitada a los operadores asociativos, y en todos los demás casos, es mejor escribir el bucle de acumulación de forma explícita.

Answer 5

Aquí estoy ofreciendo una función genérica para múltiples intersección de conjuntos 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:])

Guido podría no les gusta reduce, pero estoy un poco aficionado a ella:)