Pairwise Set Пересечения в Python

Question

Если у меня есть переменное число наборов (назовём число п), которые имеют самое м элементов каждый, что является самым эффективным способом для вычисления попарных пересечений для всех пар наборы? Обратите внимание, что это отличается от пересечения всех n наборов.

Например, если у меня есть следующие наборы:

A={"a","b","c"} 
B={"c","d","e"} 
C={"a","c","e"} 

Я хочу, чтобы иметь возможность найти:

intersect_AB={"c"} 
intersect_BC={"c", "e"} 
intersect_AC={"a", "c"} 

Другой приемлемый формат (если он делает вещи проще) будет карта элементов в заданном наборе к наборам, которые содержат тот же элемент. Например:

intersections_C={"a": {"A", "C"}, 
       "c": {"A", "B", "C"} 
       "e": {"B", "C"}} 

Я знаю, что один из способов сделать это было бы создать словарь отображения каждого значение в объединении всех п множеств в список наборов, в которых это происходит, а затем перебирать все эти значения для создания списков, таких как intersections_C выше, но я не уверен, как это масштабируется как n увеличивается, и размеры набора становятся слишком большими.

Некоторые дополнительные справочная информация:

1. Каждое из множеств имеют примерно одинаковую длину, но и очень большой (достаточно большим, чтобы хранить их в памяти реалистическое беспокойство, и алгоритм, который позволяет избежать что было бы предпочтительным, хотя это и не обязательно)
2. Размер пересечений между любыми двумя наборами очень мал по сравнению с самими размерами множеств
3. Если это помогает, мы можем предположить все, что нам нужно, относительно порядка наборы ввода.

Answer 1

это должен делать то, что вы хотите

import random as RND 
import string 
import itertools as IT 

фиктивные некоторые данные

fnx = lambda: set(RND.sample(string.ascii_uppercase, 7)) 
S = [fnx() for c in range(5)] 

генерировать список индексов множеств в S так, что наборы могут быть ссылки более сжато ниже

idx = range(len(S)) 

получить все возможные уникальные пары предметов в S; Однако, так как множество пересечения коммутативности, мы хотим комбинации, а не перестановки

pairs = IT.combinations(idx, 2) 

написать функция выполняет пересечение множеств

nt = lambda a, b: S[a].intersection(S[b]) 

сложите эту функцию по парам & ключевых результат от каждой функции вызывает ее аргументы

res = dict([ (t, nt(*t)) for t in pairs ]) 

приведенный ниже результат, отформатированный по первому варианту, указанному в OP, представляет собой словарь, в котором значения являются множеством пересечений двух последовательностей; каждый значения ключом в кортеж, состоящий из двух индексов тех последовательностей

это решение, на самом деле просто две строки кода: (I) Вычислить перестановки; (ii) затем применить некоторую функцию к каждой перестановке, сохраняя возвращаемое значение в контейнере структурированного контейнера (значение ключа)

Объем памяти этого решения минимален, но вы можете сделать еще лучше, возвращая выражение генератора в последний шаг, т.е.

res = ((t, nt(*t)) for t in pairs) 

обратите внимание, что при таком подходе, ни последовательность пар, ни соответствующих пересечениях были выписаны в памяти - то есть, обе пары и разрешением являются итераторы.

Answer 2

Если мы можем предположить, что наборы входных данных упорядочены, подход с псевдо-объединением кажется многообещающим. Рассматривая каждый набор как отсортированный поток, продвигайте потоки параллельно, всегда только продвигая те, где значение является самым низким среди всех текущих итераторов. Сравните каждое текущее значение с новым минимумом при каждом продвижении итератора и дамте совпадения в коллекции того же элемента.

Answer 3

Как насчет использования метода пересечения множества. См. Ниже:

A={"a","b","c"} 
B={"c","d","e"} 
C={"a","c","e"} 

intersect_AB = A.intersection(B) 
intersect_BC = B.intersection(C) 
intersect_AC = A.intersection(C) 

print intersect_AB, intersect_BC, intersect_AC