合并至少共享 2 个元素的集合的算法

StackOverflow https://stackoverflow.com/questions/312912

  •  10-07-2019
  •  | 
  •  

题

给定一个集合列表：

  • 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 个元素的所有集合的最有效方法是什么？我认为这类似于连接组件问题。所以结果是：

  • [ 1, 2, 3, 4, 5, 6, 7, 14, 15, 16, 17] (S_1 联合 S_2 联合 S_5)
  • [ 8, 9, 10, 11 ]
  • [ 1, 8, 12, 13 ] （S_4 与 S_1 共享 1，与 S_3 共享 8，但不合并，因为它们只共享一个元素）

简单的实现是 O(N^2)，其中 N 是集合的数量，这对我们来说是行不通的。这需要对数百万组有效。

有帮助吗？

解决方案 

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.

我的头脑在说这是关于订单（2N ln N）。对此持保留态度。

其他提示

如果您可以对集合中的元素进行排序，则可以考虑使用 归并排序 在片场。唯一需要的修改是在合并阶段检查重复项。如果找到，只需丢弃重复的即可。由于合并排序的时间复杂度为 O(n*log(n))，因此与朴素的 O(n^2) 算法相比，这将提供更快的速度。

然而，为了真正有效，您应该维护一个排序集并保持其排序，以便您可以跳过排序阶段并直接进入合并阶段。

我不明白如何在小于 O(n^2) 的时间内完成此操作。

每个集合都需要与其他集合进行比较，看看它们是否包含 2 个或更多共享元素。这是 n*(n-1)/2 次比较，因此 O(n^2)，即使共享元素的检查需要常数时间。

在排序中，简单的实现是 O(n^2)，但您可以利用有序比较的传递性质（因此，例如，您知道快速排序的下分区中的任何内容都不需要与上分区中的任何内容进行比较，因为它已经与枢轴进行了比较）。这就是导致排序时间复杂度为 O(n * log n) 的原因。

这不适用于此处。因此，除非集合中有一些特殊的东西允许我们根据之前的比较结果跳过比较，否则一般情况下它的时间复杂度为 O(n^2)。

保罗.

一侧注释：这取决于这种情况发生的频率。如果大多数对集合 做 共享至少两个元素，在逐步进行比较的同时构建新集合可能是最有效的，如果它们与条件不匹配，则将其丢弃。如果大多数对 不要 共享至少两个元素，然后推迟新集合的构建，直到条件得到确认可能会更有效。

如果您的元素本质上是数字，或者可以自然排序（即您可以分配一个值，例如 1、2、42 等...），我建议对合并集使用基数排序，并进行第二次遍历以获取唯一元素。

该算法的复杂度应该是 O(n)，并且您可以使用按位移位运算符和位掩码对基数排序进行相当多的优化。我已经为我正在做的一个项目做了类似的事情，它的效果就像一个魅力。

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top