获取在python中彼此相交的集合的列表的列表

Andrea Aquino 发表于 Dev

安德里亚·阿基诺（Andrea Aquino）

给定一个集合列表，我想得到一个相互交叉的集合列表的列表。基本上，我想要的是列表st的列表，该列表用于输出中的每个列表，该列表中的所有集合与同一列表中的至少另一个集合具有非空交集。

我希望我能够解释我的问题。希望下面的示例以及该帖子的其余部分可以进一步阐明它。

鉴于

sets = [
    set([1,3]), # A
    set([2,3,5]), # B
    set([21,22]), # C
    set([1,9]), # D
    set([5]), # E
    set([18,21]), # F
]

我想要的输出是：

[
    [
        set([1,3]), # A, shares elements with B
        set([2,3,5]), # B, shares elements with A 
        set([1,9]), # D, shares elements with A
        set([5]), # E shares elements with B
    ],
    [
        set([21,22]), # C shares elements with F
        set([18,21]), # F shares elements with C
    ]
]

输出中集合的顺序无关紧要。

我想用一个非常快的算法来实现这个目标。性能是我的首要要求。

目前，我的解决方案创建的图形的节点数与原始列表中的节点数相同。然后，如果这些集合具有非空交集，则在此图中在代表集合A和B的节点之间创建一条边。比它计算出这样一个图的连接组件，它给了我预期的结果。

我想知道是否有一种不涉及图形的算法来实现此目的的更快方法。

最好，安德里亚

阿比吉特

就像@MartijnPieters正确说的那样，问题需要图形，而networkx将助您一臂之力。

突出点

图的节点应设置
如果集相交，则图之间存在边
从结果图中找到所有连接的组件

实作

def intersecting_sets(sets):
    import networkx as nx
    G = nx.Graph()
    # Nodes of the graph should be hashable
    sets = map(frozenset, sets)
    for to_node in sets:
        for from_node in sets:
            # off-course you don't want a self loop
            # and only interested in intersecting nodes 
            if to_node != from_node and to_node & from_node:
                G.add_edge(to_node, from_node)
    # and remember to convert the frozen sets to sets
    return [map(set, lst) for lst in nx.connected_components(G)]

输出量

>>> intersecting_sets(sets)
[[set([2, 3, 5]), set([1, 3]), set([5]), set([1, 9])], [set([21, 22]), set([18, 21])]]
>>> pprint.pprint(intersecting_sets(sets))
[[set([2, 3, 5]), set([1, 3]), set([5]), set([1, 9])],
 [set([21, 22]), set([18, 21])]]

本文收集自互联网，转载请注明来源。

如有侵权，请联系[email protected] 删除。