algorithm - 用于查找严格子集的快速数据结构(从给定列表中)

Question

我有一大组集合，例如{{2,4,5} , {4,5}, ...}。 给定这些子集之一，我想遍历所有其他子集，这些子集是该子集的严格子集。也就是说，如果我对集合 A 感兴趣，例如{2,4,5}，我想找到所有集合 B 其中相对补集 B/A = {}， 空集.一些可能性可能是 {2,4}、{2,5} 但不是 {2,3}

我当然可以线性搜索并每次都检查，但我正在为较大的集合和子集(如果重要的话)寻找一个有效的数据结构。子集的数量通常为数以万计，但如果它有所不同，我会对可能达到数亿的情况感兴趣。子集的大小通常为 10 秒。

我正在用 C++ 编程

谢谢

Answer 1

从数学上讲，您应该构建 Hasse diagram对于你的集合，这将是部分有序的集合，顶点是你的集合，箭头是包含的。本质上，您想创建一个 directed, acyclic graph带箭头 A --> B如果A严格包含 B并且没有 C这样 A严格包含 C和 C严格包含 B .

这实际上是一个排名偏序集，这意味着您可以根据集合的基数跟踪有向图的“级别”。这有点像创建一个哈希表以跳转到正确的集合。

来自 A , 只需在图中做一个 BFS 来找到 A 的所有适当子集.

如何实现:(伪代码)

for (C in sets) {
    for (B in HasseDiagram at rank rank(C)+1) {
      if (C contains B)
        addArrow(C,B)
    }
    for (A in HasseDiagram at rank rank(C)+1) {
      if (C contains A)
        addArrow(A,C)
    }
    addToDiagram(C)
}

为了使这个和所有子例程更快，您可以将每个集合编码为二进制，其中数字为 i。是1如果i在C和 0否则。这使得测试遏制和确定等级变得微不足道。

如果您拥有所有可能的子集，上述方法有效。由于您可能会遗漏一些，因此您必须检查更多内容。对于伪代码，您需要更改 rank(C)-1到最大整数 l < rank(C)这样 HasseDiagram 的某些元素具有等级 l ，对于 rank(C)+1 同样如此.然后，当您添加集合时 C到图:

1. 如果 A封面 C , 那么你只需要检查排名较低的集合 B A 也包括在内.

2. 如果 C封面 B , 那么你只需要检查排名更高的集合 A这也涵盖了 B .

通过“X 覆盖 Y ”我的意思是有一个箭头 X -> Y ，不仅仅是一条路径。

此外，当您插入 C在 A 之间和 B使用上述检查之一，您需要删除箭头 A --> B当你添加 A --> C和 C --> B .