c++ - 检查子集是否包含给定子集列表的快速方法

Question

我的问题如下

我有一组K元素

这个集合的每个子集都由 std::bitset 的一个实例表示(第 i 位为真 = 子集中有元素 i)

我有一个输入子集 I 和一个子集列表 S1...Sn

我想返回 S1...Sn 中的项目，这样 Si 就包含在 I 中。(也就是说，每次 Si 有一点为真时，它也必须在 I 中为真)

显然这可以在 K*n 中完成，方法是对每个 S 子集独立地进行相同的检查。

但是，有没有一种通用的方法可以做得更好？我很确定这是可能的，因为在我的例子中，子集列表 S1...Sn 始终相同并且可以进行预处理。 我确定可以将子集存储在特定的数据结构(树？特里？)中，这样我就可以一次性丢弃很多相同的数据，等等

example :
K = 5

I = [1,1,0,1,0]

S1 = [1,0,0,0,0]
S2 = [1,1,0,1,0]
S3 = [1,1,1,0,0]

the ouput should return S1,S2 (not S3!)

我有一个常量集 S1,S2,...,Sn，并在同一组上运行 I 的不同查询。

编辑: 我在说什么的例子: 例如，如果 S1 包含在 S2 中:检查 S1 是否包含在 I 中:如果不包含，则 S2 不能包含在 I 中(无需检查) 如果 S3 是 S1 和 S2 的并集:如果 S1 和 S2 包含在 I 中，那么 S3 也包含

Answer 1

构建二叉树T所有 S1...Sn其中每个级别 k 有两个儿子节点，取决于是否 S有一个 0或 1在位k .树的叶子都是你的S1...Sn .

给定一个输入子集 I让我们来看看Ik (位置 k 的元素):if Ik==0您选择 T 的子树在级别K对应0。如果Ik==1您选择 T 的两个子树在级别K .在 T 上以这种方式进行，直到到达所有叶子。

在最坏的情况下，你会做出 O(n+k)给定 I 的操作.

自 S1...Sn不会改变，构建树 T是一次性操作。

编辑:我的回答太草率了。树 T超过n叶子，它有2^k=m树叶。但是我们可以删除不在S1...Sn中的叶子。和死去的子树。这将成本分析带到O(2^k)但实际上我们将拥有更少的节点。现在分析变得更难了，它是否值得取决于 m 之间的比率。和 n ;

我提出了一种不同的分析方法:认为在级别 k 我们丢弃所有子集 S在 k 级别具有无效位在常数时间内，但我们必须在 O(n) 内这样做每个级别的子树。由于此操作重复 k最大成本的倍数为 O(kn) ，但平均而言有效程度较低。