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

267

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

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

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

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

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

user116293
источник

Ответы:

454

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

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

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

u = set.intersection(*setlist)

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

Обратите внимание, что set.intersectionэто не статический метод, но он использует функциональную нотацию для применения пересечения первого набора с остальной частью списка. Так что, если список аргументов пуст, это не удастся.

STH
источник
65

Начиная с 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])
Майк Грэм
источник
24

Очевидно, 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}
Томас Але
источник
12

Если у вас нет 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 приобрел лямбду, lower (), filter () и map (), любезно (я полагаю) хакера Lisp, который пропустил их и представил рабочие исправления. Но, несмотря на ценность PR, я думаю, что эти функции должны быть вырезаны из Python 3000.

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

Айман Хуриех
источник
8
Обратите внимание, что Гвидо говорит, что использование reduce«ограничено ассоциативными операторами», что применимо в этом случае. reduceочень часто трудно понять, но &не все так плохо.
Майк Грэм,
Проверьте python.org/doc/essays/list2str для полезных оптимизаций, включая снижение. В общем, его можно использовать для создания списков, наборов, строк и т. Д. Также стоит посмотреть github.com/EntilZha/PyFunctional
Andreas
Обратите внимание, что вы можете оптимизировать, разорвав цикл, когда resultон пуст.
bfontaine
1

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

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, но мне это нравится :)

tzot
источник
Вы должны проверить длину setsвместо того, чтобы пытаться получить sets[0]и поймать IndexError.
bfontaine
Это не простая проверка; a_setиспользуется при окончательном возврате.
tzot
Вы не можете сделать return reduce(sets[0], sets[1:]) if sets else set()?
17
Да, спасибо. Код должен измениться, потому что следует избегать полагаться на try/ except, если это возможно. Это запах кода, он неэффективен и может скрывать другие проблемы.
17
0

Ответ Жан-Франсуа Фабра set.intesection (* list_of_sets), безусловно, является наиболее пиктоническим и справедливо принятым ответом.

Для тех, кто хочет использовать Reduce, также будет работать следующее:

reduce(set.intersection, list_of_sets)

Minas
источник