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

Question

首先，抱歉标题有些模糊不清。

假设我有以下一组集合：

第一组

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

第二组

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

对于“Group 1”中的每个集合（称为“s”），我需要查找“Group 2”中的集合（称为“m”），使得“m”是“s”的子集。对于我的示例，答案将是：

s1 -> m2
s2 -> nothing

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

有什么建议吗？

- Luchian Grigore

---

所以，在你的例子中，它只应该返回m2，这是s1的一个子集？ - crush

@crush 是的，我已经发布了我的示例的解决方案。 - Luchian Grigore

我不确定我理解了。你是说m1是s1的子集，还是反过来？看起来s1是m1的子集。但是s2又是m3的子集，那么你不是应该有s2->m3吗？如果我误解了，请原谅。 - Patrick87

@Patrick87 对不起，是我的错误。应该是m2，而不是m1。已更正。 - Luchian Grigore

你能使用排序列表并使用二分搜索吗？ - crush

Answer 1

第一步是按基数（即大小）对组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是“Group 2”中集合的数量，S是“Group 1”中集合的数量，R是“Group 1”中最大集合的大小。

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

- mcmcc

---

如果你要给我点踩，那没关系，但请至少给出一些理由。我写的有错吗？ - mcmcc

嗯...我们这里受到了一个连续的恶意投票者的困扰。有些人就是不愿意友好相处 :| - Branko Dimitrijevic

@BrankoDimitrijevic：我曾经回答过一个类似的问题。大部分答案都被无故地踩了两次，而且没有任何解释。虽然有点奇怪，但大多数人在这个“游戏”中还是玩得很公平。这是一个很好的社区。 - Mark Wilkins

Answer 2

你没有具体说明你的暴力算法的效率如何。只要你使用std::命名空间中的集合查询函数，它们很可能是尽可能高效的。 例如测试set_intersection( s1.begin(), s2.end(), m1.begin(), m1.end() )是否等价于m1。

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

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

- Matt T

Answer 3

你的集合经常被修改还是只读/大多数情况下只读？

• 如果经常被修改，std::set 是修改和排序性能之间的良好平衡。
• 如果只读或大多数情况下只读，可以使用排序的 std::vector。排序很昂贵，但实际上比在 std::set 中构造整个树更便宜，因此如果你不经常这样做，性能会更好。

一旦你创建了排序的容器（无论是“自动排序”的 std::set 还是手动排序的 std::vector），你可以使用 std::includes 测试子集。顺便说一句，如果你需要找到 真正的 子集，之后可以比较元素计数。

- Branko Dimitrijevic

---

我甚至不知道std::includes()的存在。我想现在我需要修改我的回答了... - mcmcc

Answer 4

你可以尝试这样做：

步骤：

• 创建一个包含两个组中所有对象的数组
• 将每个s和m转换为位数组，其中array(i)=1表示集合包含object(i)，否则为0
• 如果m(k) AND s(j) = m(k)，则m(k)是s(j)的子集

- D. Cannone