Подсчет пересечений для всех комбинаций в списке наборов

Question

У меня есть набор наборов. Я хочу найти количество элементов, которые находятся только в пересечении для каждой комбинации множеств. Я в основном хочу сделать то же самое, что создавать числа на диаграмме Венна.

Основной пример может сделать его более ясным.

a = set(1,2,5,10,12) 
b = set(1,2,6,9,12,15) 
c = set(1,2,7,8,15) 

я должен в конечном итоге с числом элементов найдено только в:

• в
• б
• с
• пересечение и б
• пересечение a и c
• пересечение b и c
• пересечение а, Ь и с

Не-расширяемый способ сделать это

num_a = len(a - b - c) # len(set([5,10])) -> 2 
num_b = len(b - a - c) # len(set([6,9])) -> 2 
num_c = len(c - a - b) # len(set([7,8])) -> 2 

num_ab = len((a & b) - c) # 1 
num_ac = len((a & c) - b) # 0 
num_bc = len((b & c) - a) # 1 

num_abc = len(a & b & c) # 2 

В то время как это работает на 3-х наборов моя коллекция наборов не является статичным.

Answer 1

IIUC, что-то, как это должно работать:

from itertools import combinations 

def venn_count(named_sets): 
    names = set(named_sets) 
    for i in range(1, len(named_sets)+1): 
     for to_intersect in combinations(sorted(named_sets), i): 
      others = names.difference(to_intersect) 
      intersected = set.intersection(*(named_sets[k] for k in to_intersect)) 
      unioned = set.union(*(named_sets[k] for k in others)) if others else set() 
      yield to_intersect, others, len(intersected - unioned) 


ns = {"a": {1,2,5,10,12}, "b": {1,2,6,9,12,15}, "c": {1,2,7,8,15}} 
for intersected, unioned, count in venn_count(ns): 
    print 'len({}{}) = {}'.format(' & '.join(sorted(intersected)), 
            ' - ' + ' - '.join(sorted(unioned)) if unioned else '', 
            count) 

который дает

len(a - b - c) = 2 
len(b - a - c) = 2 
len(c - a - b) = 2 
len(a & b - c) = 1 
len(a & c - b) = 0 
len(b & c - a) = 1 
len(a & b & c) = 2 

Answer 2

Вы можете использовать itertools.combinations, чтобы получить все возможные комбинации. http://docs.python.org/2/library/itertools.html

Answer 3

Я бы попробовать с помощью битовых масок:

sets = [ 
    set([1,2,5,10,12]), 
    set([1,2,6,9,12,15]), 
    set([1,2,7,8,15]), 
] 

d = {} 

for n, s in enumerate(sets): 
    for i in s: 
     d[i] = d.get(i, 0) | (1 << n) 

for mask in range(1, 2**len(sets)): 
    cnt = sum(1 for x in d.values() if x & mask == mask) 
    num = ','.join(str(j) for j in range(len(sets)) if mask & (1 << j)) 
    print 'number of items in set(s) %s = %d' % (num, cnt) 

результаты для вашего ввода:

number of items in set(s) 0 = 5 
number of items in set(s) 1 = 6 
number of items in set(s) 0,1 = 3 
number of items in set(s) 2 = 5 
number of items in set(s) 0,2 = 2 
number of items in set(s) 1,2 = 3 
number of items in set(s) 0,1,2 = 2