algorithm - 加入具有相似元素的多个子集的最快方法是什么？

Question

我有一个包含 500 多个子集的列表，每个子集具有 1 到 500 个值(整数)。所以我有类似的东西:

{1, 2, 3 }
{2, 3}
{4, 5}
{3, 6, 7}
{7, 9}
{8, 4}
{10, 11}

运行代码后我想得到:

{1, 2, 3, 6, 7, 9}
{4, 5, 8}
{10, 11}

我写了简单的代码[here]将每个子集与每个子集进行比较，如果它们相交，它们就连接在一起，否则不相交。 小规模没问题，但如果数据量很大，就需要很长时间。

请问，您能提出任何改进建议吗？

附言我不擅长数学或逻辑，大 O 符号对我来说是希腊语。对不起。

Answer 1

您正试图在图中找到连通的分量，每个输入集代表一组完全连通的节点。这是一个简单的实现:

sets = [{1, 2, 3 },{2, 3},{4, 5},{3, 6, 7},{7, 9},{8, 4},{10, 11}]
allelts = set.union(*sets)
components = {X: {X} for X in allelts}
component = {X: X for X in allelts}
for S in sets:
    comp = sorted({component[X] for X in S})
    mergeto = comp[0]
    for mergefrom in comp[1:]:
        components[mergeto] |= components[mergefrom]
        for X in components[mergefrom]:
            component[X] = mergeto
        del components[mergefrom]

这导致组件有一个组件列表(以它们的最小元素为键)，并且组件存储每个元素的组件:

>>> print(components)
{1: {1, 2, 3, 6, 7, 9}, 4: {8, 4, 5}, 10: {10, 11}}
>>> print(component)
{1: 1, 2: 1, 3: 1, 4: 4, 5: 4, 6: 1, 7: 1, 8: 4, 9: 1, 10: 10, 11: 10}
>>>