питона найти наборы с общими элементами

Question

Мои данные представляют собой набор frozenset, например,

data = set([frozenset([1,2,3,4]), frozenset([3,4,5,6,7,8]), frozenset([100,200]), frozenset([1,1000, 2000])]) 

и предполагаемый результат является набор frozenset с повторяющимися элементами, т.е.

result = set([frozenset([1,2,3,4]), frozenset([3,4,5,6,7,8]), frozenset([1,1000, 2000])]) 

Здесь frozenset([100,200]) удаляется из-за того, что он не содержит никаких элементов с другими фенизаторами. Каков эффективный способ реализации этого?

Answer 1

Вы можете построить dict элементов набора, чтобы подсчитать, сколько раз они будут найдены, а затем отбросить любые frozenset, где подсчет всех его элементов равен 1. collections.Counter было бы удобно для этого.

Это то, что имеет O(n), где n - общее количество элементов во всех наборах.

from collections import Counter 

data = set([frozenset([1,2,3,4]), frozenset([3,4,5,6,7,8]), frozenset([100,200]), frozenset([1,1000, 2000])]) 
counts = Counter(elt for fs in data for elt in fs) 
result = {fs for fs in data if any(counts[elt] > 1 for elt in fs)} 

# {frozenset({1, 2, 3, 4}), frozenset({1000, 1, 2000}), frozenset({3, 4, 5, 6, 7, 8})} 

Answer 2

Я бы сделал множество понимания с проверкой, как, что (для каждого элемента, проверьте, если она имеет общие элементы с по меньшей мере 1 другим элементом):

data = set([frozenset([1,2,3,4]), frozenset([3,4,5,6,7,8]), frozenset([100,200]), frozenset([1,1000, 2000])]) 

new_data = {x for x in data if any(not x.isdisjoint(y) for y in data if y!=x)} 

print(new_data) 

результат:

{frozenset({1, 2, 3, 4}), frozenset({3, 4, 5, 6, 7, 8}), frozenset({1000, 1, 2000})} 

Там может быть более эффективные решения, но, по крайней мере, часть disjoint обрабатывается эффективных set подпрограмм

Answer 3

Это моя версия, она не имеет особых преимуществ, но вы можете найти ее более читаемой.

data = set([frozenset([1,2,3,4]), frozenset([3,4,5,6,7,8]), frozenset([100,200]), frozenset([1,1000, 2000])]) 
result = set() 

for item in data: 
    for element in item: 
     for other_item in data: 
      if item != other_item and item not in result: 
       if element in other_item: 
        result.add(item) 
        break 
>>>print(result) 
>>>{frozenset({1, 2, 3, 4}), frozenset({1000, 1, 2000}), frozenset({3, 4, 5, 6, 7, 8})}