从一组集合中查找集合子集的最佳方法-解网

问：

首先，对不起，标题模棱两可。

假设我有以下一组集合：

第 1 组

s1 = ( x1, y1 )
s2 = ( x2 )

第 2 组

m1 = ( x1, y1, y2 )
m2 = ( x1 )
m3 = ( x1 , x2 )

对于 - 调用集合中的每个集合，我需要找到 - 调用它 - 中的集合，以便它是的子集。Group 1sGroup 2mms

所以，对于我的例子，答案是：

s1 -> m2
s2 -> nothing

目前，我将值存储在中，但如果需要，我可以更改它。此外，集合可能会变大，因此算法需要高效。目前，我有一种蛮力方法，我并不完全满意。std:set

有什么建议吗？

C++ 算法子集

你可以比这更有效率，因为你不想要匹配元素的副本，只是知道它们都出现了。这可以通过复制 set_intersection 的代码来完成，但将实现更改为简单地计算匹配元素的数量，而不是将它们复制出来。然后，如果计数与 m 的大小相同，则您有一个匹配项。

至于容器，对于大型收藏，我通常更喜欢排序的 deque 而不是集合。内存在堆上的分布要少得多，这有助于缓存。它还避免了底层树的开销。当容器创建一次，但被多次搜索时，这尤其有用。

1赞 mcmcc 2/16/2012 #2

第一步是根据基数（即大小）对第 1 组进行排序。然后算法是以下顺序的：

foreach std::set M in "Group 2" {
  foreach std::set S in "Group 1" and S.size()>=M.size() {  // replace with binary search
     if ( std::includes(S.begin(),S.end(),M.begin(),M.end()) )
       { /* M is a subset of S */ }
    }
  }
}

这应该具有时间复杂度~O（MSR），其中M是“组2”中集合的#，S是“组1”中集合的#，R是“组#1”中最大集合的大小。

编辑：我只是想到，使用而不是调用（按顺序迭代）可能更有效，但我认为只有当 M.size（）比 S.size（）小得多时才是正确的——O（M+S）与 O（MlogS）。S.find()std::includes()

从一组集合中查找集合子集的最佳方法

Best way to find a subset of a set from a group of sets

第 1 组

第 2 组

评论

评论

评论