Лучший способ найти пересечение нескольких множеств? - PullRequest
Новая
       33

Лучший способ найти пересечение нескольких множеств?

215 голосов
/ 30 марта 2010

У меня есть список наборов: 

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

Я хочу s1 ∩ s2 ∩ s3 ...

Я могу написать функцию для этого, выполнив серии попарно s1.intersection(s2) и т. Д.

Есть ли рекомендуемый, лучший или встроенный способ?

Ответы [ 5 ]

378 голосов
/ 30 марта 2010

Начиная с версии Python 2.6 вы можете использовать несколько аргументов для set.intersection(), например 

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

Если наборы находятся в списке, это означает: 

u = set.intersection(*setlist)

, где *a_list - это расширение списка

61 голосов
/ 30 марта 2010

Начиная с 2.6, set.intersection занимает произвольно много итераций. 

>>> 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])
17 голосов
/ 29 февраля 2012

Понятно, set.intersection - это то, что вы хотите здесь, но в случае, если вам когда-нибудь понадобится обобщение «взять сумму всех этих», «взять произведение всех этих», «взять xor всех этих», что Вы ищете reduce функция: 

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

или 

print(reduce((lambda x,y: x&y), [{1,2,3},{2,3,4},{3,4,5}])) # = {3}
11 голосов
/ 30 марта 2010

Если у вас нет Python 2.6 или выше, альтернатива - написать явный цикл 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])

Вы также можете использовать reduce: 

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

Однако многим программистам на Python это не нравится, включая самого Гвидо :

Около 12 лет назад Python приобрел лямбду-редукторы (Reduce (), Filter () и Map ()), любезно (я полагаю) хакер Lisp, который пропустил их и представил рабочие исправления Но, несмотря на значение PR, я думаю, что эти функции должны быть вырезаны из Python 3000.

Так что теперь уменьшаем (). Это на самом деле тот, который я всегда ненавидел больше всего, потому что, за исключением нескольких примеров, включающих + или *, почти каждый раз, когда я вижу вызову redu () с нетривиальным аргументом функции, мне нужно взять ручку и бумагу, чтобы представьте диаграмму, что на самом деле подается в эту функцию, прежде чем я пойму, что должен делать redu (). Поэтому, на мой взгляд, применимость метода limit () в значительной степени ограничена ассоциативными операторами, и во всех других случаях лучше выписать цикл накопления явно.

1 голос
/ 01 апреля 2010

Здесь я предлагаю универсальную функцию для пересечения нескольких множеств, пытаясь воспользоваться лучшим из доступных методов: 

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

Гвидо может не нравиться reduce, но мне это очень нравится

...