Подсчет уникальных пересекающихся множеств из списка

У меня есть двумерный список чисел обоих размеров различной длины. Они представляют собой открытые порты для хостов. Ниже приведен список открытых портов на 4 разных хостах:

ports = [[22,23],[22],[22,23,80],[23,80]] 

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

 Ports -> Count 22 -> 3 22, 23 -> 2 23 -> 3 23, 80 -> 2 80 -> 2 

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

  • Создать матрицу пересечений между каждым хостом

  • Извлечь / сгладить матрицу, чтобы включить только уникальные множества, т. Е. Не обратный порядок.

     -- a AND b, b AND a => a AND b 
  • Создайте новый список, содержащий каждый уникальный набор портов из списка (extract / flatten) и количество раз, которое было установлено.

Используя рецепт poweret от itertools :

 from collections import Counter from itertools import chain, combinations def powerset(iterable): "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)" s = list(iterable) return chain.from_iterable(combinations(s, r) for r in range(len(s)+1)) def port_table(ports): d = Counter() for portseq in ports: for subset in powerset(sorted(portseq)): if subset: d[subset] += 1 return d 

В принципе, powerset дает возможность увеличивать все возможные подмножества (включая пустую, а значит, и if subset: пропустить), а затем для каждого подмножества, которое мы видим в каждом списке портов, мы увеличиваем объект Counter . Затем это производит

 >>> ports = [[22,23],[22],[22,23,80],[23,80]] >>> table = port_table(ports) >>> for port, count in sorted(table.items()): ... if count > 1: ... print port, '->', count ... (22,) -> 3 (22, 23) -> 2 (23,) -> 3 (23, 80) -> 2 (80,) -> 2