用于查找严格子集的快速数据结构(来自给定列表)

Question

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

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

我用C++编程

谢谢

Answer 1

在数学上,你应该为你的集合构造Hasse图,它将是部分有序的集合,其顶点是你的集合和箭头给出的包含.从本质上讲,你要创建一个针对无环图有一个箭头A --> B,如果A严格包含B并没有C这样A严格包含C 和C严格包含B.

这实际上将是一个排名的poset,这意味着你可以根据集合的基数来跟踪有向图的"级别".这有点像创建哈希表以跳转到正确的集合.

从中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是1if iin 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.

Answer 2

我建议将所有集合存储在树中。树的每个节点将代表包含指定初始整数列表的所有集合。我会让节点包含以下信息：

1. 树中此时或下方最小集合中的附加元素数。（0 表示该节点在树中。）
2. 表示树中此子集下方所有子集的交集的位集。
3. 指向数组的指针，将较大的整数映射到包含它作为下一个元素的子树。作为一种特殊情况，如果树中只有一个子集低于此子集，则此指针可能为空。（无需填写树中未填充的部分。）

给定这棵树和一个子集，您可以对集合的所有子集进行递归和回溯搜索。在搜索中，您从子集的第一个元素开始，查找包含该元素的所有子集，然后搜索不包含该元素的所有子集。

构建这棵树最多需要时间和空间，O(n * m * k)其中n子集m的数量是每个子集的平均元素数，k是集合中元素的整体大小。使用比k元素子集的可能范围小得多的随机集合集，您将不会构建树的大部分内容，而这将O(n * m)用于您的树。

理论上遍历这棵树可能是时间O(n)。 但在实践中，您会很早就修剪树的分支，并且不会遍历大多数其他子集。信封计算的背面表明，如果你有n一个k元素宇宙的随机集合，那么树的搜索是。（对于每个整数，有一半时间在您的集合中，您正在搜索 的子集并将搜索分成 2 个，一半时间不在您的集合中，您消除了一半的空间。在整数之后，您已经搜索了大小集的集合。因此，当您将搜索降低到单个其他子集进行比较时，有n << 2kO(n0.5k)j2j/22-jnO(n0.5)搜索进行。位图的最终对比是O(k).)

注意：我确信这个包络计算的平均性能是每个，但收敛速度非常慢。更准确地说，我怀疑性能的算术平均值是. 但那一块需要很长时间才能收敛。o(n0.5+epsilon)epsilon > 0n0.5 + O(sqrt(log(n))))sqrt(log(n))

请注意，使用树中此时或下方最小集合中附加元素的数量可以让您的搜索轻松过滤掉所有太大而不能成为子集的集合。根据您的数据集，这可能会或可能不会导致有用的加速。