合并共享至少2个元素的集合的算法 [英] Algorithm for merging sets that share at least 2 elements

问题描述

给出一组列表：

• S_1：[1，2，3，4]


• S_2：[3、4、5、6、7]


• S_3：[8、9、10、11]


• S_4 ：[1，8，12，13]


• S_5：[6，7，14，15，15，16，17]

• S_1 : [ 1, 2, 3, 4 ]
• S_2 : [ 3, 4, 5, 6, 7 ]
• S_3 : [ 8, 9, 10, 11 ]
• S_4 : [ 1, 8, 12, 13 ]
• S_5 : [ 6, 7, 14, 15, 16, 17 ]

最有效的方法是合并所有共享至少2个元素的集合？我想这类似于连接组件的问题。因此结果将是：

What the most efficient way to merge all sets that share at least 2 elements? I suppose this is similar to a connected components problem. So the result would be:

• [1，2，3，4，5，6，7，14，15，16，17 ]（S_1 UNION S_2 UNION S_5）


• [8，9，10，11]


• [1，8，12，13]（S_4与S_1共享1，与S_3共享8，但由于每个元素仅共享一个元素而未合并）

天真的实现是O （N ^ 2），其中N是集合数，这对我们来说是行不通的。

The naive implementation is O(N^2), where N is the number of sets, which is unworkable for us. This would need to be efficient for millions of sets.

推荐答案

Let there be a list of many Sets named (S)

Perform a pass through all elements of S, to determine the range (LOW .. HIGH).

Create an array of pointer to Set, of dimensions (LOW, HIGH), named (M).

do
    Init all elements of M to NULL.   

    Iterate though S, processing them one Set at a time, named (Si).

        Permutate all ordered pairs in Si. (P1, P2) where P1 <= P2.
        For each pair examine M(P1, P2)
            if M(P1, P2) is NULL
                Continue with the next pair.
            otherwise
                Merge Si, into the Set pointed to by, M(P1, P2).
                Remove Si from S, as it has been merged.
                Move on to processing Set S(i + 1)

        If Si was not merged, 
            Permutate again through Si
            For each pair, make M(P1, P2) point to Si.

while At least one set was merged during the pass.

我的头是说这是关于Order（2N ln N）的。
撒上一点盐。

My head is saying this is about Order (2N ln N). Take that with a grain of salt.

这篇关于合并共享至少2个元素的集合的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！