Какой быстрый способ идентифицировать все перекрывающиеся множества? ⇐ Python

[Anonymous]

Мне нужно идентифицировать и объединить все пересекающиеся множества, чтобы в конечном итоге у меня были полностью дискретные множества, не имеющие общих значений. Наборы в настоящее время существуют в виде значений в словаре, а ключи словаря сортируются по приоритету, который необходимо сохранить.
Например, начиная со следующих наборов в словаре d :

Код: Выделить всё

d = {'b': {'b', 'f', 'a'},
'x': {'x'},
's': {'s'},
'a': {'a', 'f', 'e'},
'e': {'e'},
'f': {'f'},
'z': {'x', 'z'},
'g': {'g'}}

...Я пытаюсь объединить наборы, чтобы:

Код: Выделить всё

{'b': {'a', 'b', 'e', 'f'},
'x': {'x', 'z'},
's': {'s'},
'a': {'a', 'b', 'e', 'f'},
'e': {'a', 'b', 'e', 'f'},
'f': {'a', 'b', 'e', 'f'},
'z': {'x', 'z'},
'g': {'g'}}

...путем объединения всех наборов, которые перекрываются с другими наборами.
У меня есть код, который приводит к следующим результатам:

Код: Выделить всё

d_size = {k:len(v) for (k, v) in d.items()}
static = False
while not static:
for (k, vs) in d.items():
for v in vs:
if v == k: continue
d[v].update(vs)

static = True
for (k, v) in d_size.items():
if len(d[k]) != v:
d_size[k] = len(d[k])
static = False

. . . но это непомерно медленно для объемов наборов данных, которые ему приходится обрабатывать, которые регулярно достигают нескольких сотен тысяч строк с заданными размерами произвольной длины, но обычно менее 50 после завершения консолидации.
В конечном итоге мне нужно удалить повторяющиеся наборы, гарантируя, что я сохраняю [b]первое[/b] появление в словаре, поскольку ключи сортируются по приоритету, поэтому окончательный результат для этой игрушки пример набора:
{'b': {'a', 'b', 'e', 'f'}, 'x': {'x', 'z'}, 's': {'s'}, 'g': {'g'}}

Мне нужен только этот окончательный словарь для моих целей, поэтому я открыт для любых решений, которые не создают промежуточный словарь с повторяющимися наборами.
Наконец, эти результаты отображаются обратно в фрейм данных pandas, поэтому я открыт для использования решений, включающих pandas (или numpy). Любые другие сторонние пакеты необходимо будет сбалансировать, взвесив их влияние и пользу.

Подробнее здесь: https://stackoverflow.com/questions/790 ... pping-sets