在集合列表中查找不相交集合的对数 [英] Find number of pairs of disjoint sets in a list of sets

问题描述

问题陈述如下：给定n个集合的列表，每个集合包含k个整数，找到不交集的对数。假设集合中可能的元素为正，且在上面由c> n界定，并且假设k < 。

The problem statement is as follows: given a list of n sets, each containing k integers, find the number of pairs of disjoint sets. Suppose the possible elements of the sets are positive and bounded above by c > n, and suppose k << n.

我试图提出一种比O（kn ^ 2）更快的算法来解决这个问题，这是天真的解决方案的运行时间。

I'm trying to come up with an efficient algorithm to solve this faster than O(kn^2), which is the runtime of the naive solution.

我能想到的最佳策略是遍历列表中的每个集合，并对集合的元素进行哈希处理，以使集合中的每个元素映射为一个包含它的集合的索引集合。然后，对于迭代中的当前集合，将其c个元素用作键，并考虑由哈希表作为值给出的c个索引集的并集。这个结果索引集表示到目前为止遇到的与当前集不脱节的集数，我们可以使用它来查找不相交集的数。在整个迭代过程中求和该值可得出正确答案。但是，由于联合运算为O（n），因此此策略并不比单纯的解决方案更好。

The best strategy I could come up with involves iterating through each set in the list, and hashing the elements of the set, such that each element in the set maps to a set of the indices of the sets that contain it. Then, for the current set in the iteration, use its c elements as keys, and consider the union of the c sets of indices that are given as values by the hashtable. This resulting set of indices represents the number of sets encountered thusfar that are nondisjoint with the current set, which we can use to find the number of disjoint sets. Summing this value over the entire iteration yields a correct answer. However, since the union operation is O(n), this strategy does no better than the naive solution.

对于此问题，最有效的解决方案是什么？ p>

What is the most efficient possible solution for this problem?

推荐答案

如k<< n，可以通过以下方式降低复杂度：

As k << n, you can reduce the complexity by:

• 对每个集合进行排序，可以是n * k * log（k）


• 然后按第一个倒数第二个元素对所有集合进行排序* log（n）

现在比较需求n *（n-1）个运算，它们是：

Now comparing needs n * (n - 1) operations, which are:

• 比较s1.Last和s2.First（应该比较大多数情况，例如k<<< n）


• 或考虑到s1和s2已排序，有效地搜索k在k中最大的s1 s2交点

这篇关于在集合列表中查找不相交集合的对数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！