Melhor maneira de encontrar a interseção de vários conjuntos?

267

Eu tenho uma lista de conjuntos:

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

Quero s1 ∩ s2 ∩ s3 ...

Eu posso escrever uma função para fazer isso executando uma série de pares s1.intersection(s2), etc.

Existe uma maneira recomendada, melhor ou integrada?

user116293
fonte

Respostas:

454

No Python versão 2.6, você pode usar vários argumentos para set.intersection(), como

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

Se os conjuntos estiverem em uma lista, isso se traduzirá em:

u = set.intersection(*setlist)

onde *a_listestá a expansão da lista

Observe que nãoset.intersection é um método estático, mas isso usa a notação funcional para aplicar a interseção do primeiro conjunto com o restante da lista. Portanto, se a lista de argumentos estiver vazia, isso falhará.

sth
fonte
65

A partir da versão 2.6, set.intersectionleva arbitrariamente muitas iteráveis.

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

Claramente set.intersectioné o que você quer aqui, mas, se você precisar de uma generalização de "pegue a soma de tudo isso", "pegue o produto de todos esses", "pegue o xor de todos esses", o que você está procurando é o reducefunção:

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

ou

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

Se você não possui o Python 2.6 ou superior, a alternativa é escrever um loop 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])

Você também pode 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])

No entanto, muitos programadores de Python não gostam disso, incluindo o próprio Guido :

Há cerca de 12 anos, o Python adquiriu lambda, reduza (), filtre () e mapeie (), cortesia de (acredito) um hacker do Lisp que os perdeu e enviou os patches de trabalho. Mas, apesar do valor de RP, acho que esses recursos devem ser cortados do Python 3000.

Então agora reduza (). Na verdade, esse é o que eu mais odiei, porque, além de alguns exemplos envolvendo + ou *, quase sempre que vejo uma chamada de redução () com um argumento de função não trivial, preciso pegar papel e caneta para diagrama o que realmente está sendo alimentado nessa função antes que eu entenda o que o reduzir () deve fazer. Então, na minha opinião, a aplicabilidade de reduzir () é praticamente limitada aos operadores associativos e, em todos os outros casos, é melhor escrever explicitamente o ciclo de acumulação.

Ayman Hourieh
fonte
8
Observe que Guido diz que o uso reduceé "limitado a operadores associativos", o que é aplicável neste caso. reducemuitas vezes é difícil descobrir, mas &não é tão ruim.
Mike Graham
Confira python.org/doc/essays/list2str para otimizações úteis envolvendo redução. Em geral, ele pode ser usado bastante bem para criar listas, conjuntos, seqüências de caracteres etc. Vale a pena ver também o github.com/EntilZha/PyFunctional
Andreas
Observe que você pode otimizar interrompendo seu loop quando resultestiver vazio.
precisa saber é o seguinte
1

Aqui, estou oferecendo uma função genérica para interseção de vários conjuntos, tentando aproveitar o melhor método disponível:

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 pode não gostar reduce, mas eu meio que gosto disso :)

tzot
fonte
Você deve verificar o comprimento em setsvez de tentar acessar sets[0]e capturar o arquivo IndexError.
precisa saber é o seguinte
Esta não é uma verificação simples; a_seté usado no retorno final.
tzot
Você não pode fazer return reduce(sets[0], sets[1:]) if sets else set()?
precisa saber é o seguinte
Ha sim, obrigado. O código deve mudar porque confiar em um try/ exceptdeve ser evitado, se possível. É um cheiro de código, é ineficiente e pode esconder outros problemas.
precisa saber é o seguinte
0

Jean-François Fabre A resposta set.intesection (* list_of_sets) é definitivamente a mais pytonica e é a resposta aceita.

Para aqueles que desejam usar reduzir, o seguinte também funcionará:

reduce(set.intersection, list_of_sets)

Minas
fonte