Najlepszy sposób na znalezienie przecięcia wielu zestawów?

266

Mam listę zestawów:

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

Chcę s1 ∩ s2 ∩ s3 ...

Mogę napisać funkcję, aby to zrobić, wykonując serię par s1.intersection(s2)itp.

Czy istnieje zalecany, lepszy lub wbudowany sposób?

użytkownik116293
źródło

Odpowiedzi:

454

Począwszy od wersji 2.6 języka Python, możesz używać wielu argumentów set.intersection(), na przykład

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

Jeśli zestawy znajdują się na liście, oznacza to:

u = set.intersection(*setlist)

gdzie *a_listjest rozwinięcie listy

Zauważ, że nieset.intersection jest to metoda statyczna, ale używa ona notacji funkcjonalnej do zastosowania przecięcia pierwszego zestawu z resztą listy. Więc jeśli lista argumentów jest pusta, to się nie powiedzie.

coś
źródło
65

Począwszy od wersji 2.6, set.intersectionprzyjmuje dowolnie wiele iteracji.

>>> 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
źródło
24

Najwyraźniej set.intersectionjest to, czego chcesz tutaj, ale jeśli kiedykolwiek potrzebujesz uogólnienia „weź sumę wszystkich tych”, „weź produkt wszystkich tych”, „weź xor wszystkich tych”, to czego szukasz, to reducefunkcjonować:

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

lub

print(reduce((lambda x,y: x&y), [{1,2,3},{2,3,4},{3,4,5}])) # = {3}
Thomas Ahle
źródło
12

Jeśli nie masz języka Python 2.6 lub nowszego, alternatywą jest napisanie wyraźnej pętli 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])

Możesz także użyć reduce:

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

Jednak wielu programistów Python nie lubi tego, w tym sam Guido :

Około 12 lat temu Python nabył lambda, redukcję (), filtr () i mapę () dzięki uprzejmości (chyba) hakera Lisp, który tęsknił za nimi i przesłał działające poprawki. Ale pomimo wartości PR uważam, że te funkcje należy wyciąć z Python 3000.

Więc teraz zmniejsz (). Jest to właściwie ten, którego zawsze nienawidziłem najbardziej, ponieważ oprócz kilku przykładów obejmujących + lub *, prawie za każdym razem, gdy widzę wywołanie redukcyjne () z nietrywialnym argumentem funkcji, muszę chwycić pióro i papier, aby wykreślić, co faktycznie jest wprowadzane do tej funkcji, zanim zrozumiem, co powinna zrobić funkcja redukująca (). Tak więc, moim zdaniem, zastosowanie funkcji zmniejszania () jest w zasadzie ograniczone do operatorów asocjacyjnych, a we wszystkich innych przypadkach lepiej jest wyraźnie napisać pętlę akumulacji.

Ayman Hourieh
źródło
8
Zauważ, że Guido twierdzi, że użycie reducejest „ograniczone do operatorów asocjacyjnych”, co ma zastosowanie w tym przypadku. reducebardzo często trudno to rozgryźć, ale &nie jest tak źle.
Mike Graham
Sprawdź python.org/doc/essays/list2str, aby uzyskać przydatne optymalizacje obejmujące redukcję. Zasadniczo można go całkiem dobrze używać do budowania list, zestawów, ciągów znaków itp. Warto również zajrzeć na github.com/EntilZha/PyFunctional
Andreas
Pamiętaj, że możesz zoptymalizować, przerywając pętlę, gdy resultjest pusta.
bfontaine
1

Oto oferuję ogólną funkcję do przecinania wielu zestawów, próbując skorzystać z najlepszej dostępnej metody:

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 może nie lubić reduce, ale lubię to :)

tzot
źródło
Powinieneś sprawdzić długość setszamiast próbować uzyskać dostęp sets[0]i złapać IndexError.
bfontaine
To nie jest zwykły czek; a_setjest używany przy ostatnim zwrocie.
tzot
Nie można zrobić return reduce(sets[0], sets[1:]) if sets else set()?
bfontaine
Ha tak, dziękuję. Kod powinien ulec zmianie, ponieważ można polegać na try/, exceptjeśli możesz. Jest to zapach kodu, jest nieefektywny i może ukrywać inne problemy.
bfontaine
0

Jean-François Fabre set.intesection (* list_of_sets) odpowiedź jest zdecydowanie najbardziej pyhonickim i słusznie jest odpowiedzią zaakceptowaną.

W przypadku tych, którzy chcą użyć funkcji zmniejsz, będą również działać następujące czynności:

reduce(set.intersection, list_of_sets)

Minas
źródło