Comment trouver au mieux l'intersection de plusieurs ensembles en python?

Question

J'ai une liste d'ensembles:

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

Je veux s1 ∩ s2 s3 ...

Je peux écrire une fonction pour le faire en effectuant une série de paires s1.intersection(s2) , etc.

Existe-t-il un moyen recommandé, meilleur ou intégré?

Answer 1

A partir de la version 2.6 de Python, vous pouvez utiliser plusieurs arguments pour set.intersection() , comme

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

Si les ensembles sont dans une liste, cela se traduit par:

 u = set.intersection(*setlist)
 

Answer 2

A partir de 2.6, set.intersection prend arbitrairement beaucoup d'itérables.

 >>> 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

Il est clair que set.intersection est ce que vous voulez ici, mais au cas où vous auriez besoin d’une généralisation de "prenez la somme de tous", "prenez le produit de tous", "prenez le xor de tous", vous recherchez la fonction reduce :

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

Answer 4

Si vous ne disposez pas de Python 2.6 ou supérieur, l'alternative est d'écrire explicitement la boucle for:

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

Vous pouvez également utiliser reduce:

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

Cependant, de nombreux programmeurs Python n'aime pas, y compris Guido lui-même:

Il y a 12 ans, Python acquis lambda, réduire(), filter() et map(), avec l'aimable autorisation de (je crois) un Lisp hacker qui l'ont manqué, et soumis de travail des correctifs. Mais, en dépit de la PR de la valeur, je pense que ces caractéristiques doivent être coupés à partir de Python 3000.

Alors maintenant, réduire(). C'est en fait celui que j'ai toujours détesté le plus, parce que, en dehors de quelques exemples impliquant des + ou *, presque chaque fois que je vois un de réduire() avec un non-trivial argument de fonction, j'ai besoin de saisir stylo et du papier pour diagramme de ce fait d'être introduit dans cette fonction avant que je comprends ce que le réduire() est censé faire. Donc dans mon esprit, l'applicabilité de réduire() est assez limitée à des opérateurs associatifs, et dans tous les autres cas, il est préférable d'écrire l'accumulation de la boucle de manière explicite.

Answer 5

Ici, je propose une fonction générique pour l'intersection de plusieurs ensembles en essayant de tirer parti de la meilleure méthode 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 pourrait ne pas aimer reduce , mais je l'aime bien :)