从列表中计算唯一的交叉集

Question

我有一个二维数字列表,两个维度的长度不同.这些代表主机的开放端口.以下是显示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)列表中每个唯一的端口集以及设置发生的次数.

Answer 1

使用itertools中的powerset配方:

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