将非传递项对分组为最大(重叠)子集的算法

Question

我正在研究一种算法，将匹配的对项组合成更大的组。问题是，这些对是而不是传递的；1=2和2=3并不一定意味着1=3，但是它们是可交换的，所以1=2意味着2=1。

每个项目可以属于多个组，但每个组应该尽可能大；例如，如果1=2、1=3、1=4、1=5、2=3、3=4和4=5，那么我们将以1-2-3、1-3-4和1-4-5的组结束。

到目前为止，我想出的最好的解决方案是递归地工作:对于任何给定的项，遍历以后的每一项，如果它们匹配，则递归并遍历每个后续项，以查看它是否与您收集到的所有项匹配。(然后检查以确保没有一个更大的组已经包含了该组合，例如，在上面的示例中，我将输出4-5，然后返回并发现它们已经包含在1-4-5中)

所涉及的集合并不庞大--很少超过40或50项--但我可能在一次操作中处理数千个这样的小集合。所以在计算复杂性方面，如果它是O(n平方)或者其他什么的话，这是完全可以的，因为它不需要缩放到巨大的集合，但是我希望它在那些小的50项集上尽可能快。

不管怎么说，虽然我可以用上面的解决方案来解决问题，但我觉得这是不必要的尴尬和缓慢，所以如果有更好的方法，我很想听听。

Answer 1

如果你想要所有的极大群，那么这个问题没有次指数算法。正如https://cstheory.stackexchange.com/questions/8390/the-number-of-cliques-in-a-graph-the-moon-and-moser-1965-result所指出的，要查找的最大团的数量在图的大小上可能会呈指数增长。

如果您只想要一组覆盖所有原始关系的最大组，那么您可以在多项式时间内解决这个问题(尽管不是一个很好的界限)。

def maximal_groups (pairs):
    related = {}
    not_included = {}
    for pair in pairs:
        for i in [0, 1]:
            if pair[i] not in related:
                related[pair[i]] = set()
                not_included[pair[i]] = set()
            if pair[1-i] not in related:
                related[pair[1-i]] = set()
                not_included[pair[1-i]] = set()
        related[pair[0]].add(pair[1])
        related[pair[1]].add(pair[0])
        not_included[pair[0]].add(pair[1])
        not_included[pair[1]].add(pair[0])

    groups = []
    for item in sorted(related.keys()):
        while 0 < len(not_included[item]):
            other_item = not_included[item].pop()
            not_included[other_item].remove(item)
            group = [item, other_item]
            available = [x for x in sorted(related[item]) if x in related[other_item]]
            while 0 < len(available):
                next_item = available[0]
                for prev_item in group:
                    if prev_item in not_included[next_item]:
                        not_included[next_item].remove(prev_item)
                        not_included[prev_item].remove(next_item)
                group.append(next_item)
                available = [x for x in available if x in related[next_item]]
            groups.append(group)
    return groups

print(maximal_groups([[1,2], [1,3], [1,4], [1,5], [2,3], [3,4], [4,5]]))