用于查找集合中存在的子集的数据结构

Question

考虑我们有从

到

的整数集的

子集。例如，

N = 5, n = 3

s_1 = {1, 4}
s_2 = {2, 4, 5}
s_3 = {1, 5}

这些子集是固定的，永远不会改变（我提前知道所有这些子集，并且有任意数量的时间来预先计算我将来需要的任何东西）。

有一个过程获取从 1 到 N 的任意整数子集（不是来自上面的列表），并且需要从上面的列表返回子集，以便它们的所有元素都在输入中。例如，对于输入

{1, 2, 3, 5}

，输出必须是

s3

，对于输入

{1, 4, 5}

，输出必须是

s_1, s_3

。

我需要一种复杂性不依赖于子集数量的算法（

）（取决于结果的大小是可以的）。

~

1 000 000

、

~

100 000

的期望值，子集的平均大小为

（它是预先已知的常数），典型输入的平均大小为

。结果的预期大小为

0-5

（几乎总是

或

）。

目前，对于从

到

的每个数字，我预先计算一个数组，用于存储该数字所包含的子集。当我获得每个数字的输入时，我会找到子集并计算我拥有的值的数量已经从这个子集中遇到过。由于我知道每个子集的大小以及输入中的所有数字都是唯一的，因此我可以轻松了解是否遇到了子集中的所有数字。

问题是，例如，如果每个子集中都有一个数字，每次我在输入上遇到它时，我都必须迭代所有子集，即使它们不太可能全部保留在当我消耗完整个输入后，我的候选列表。

添加

一个更简单的任务（我也对此感兴趣）：不是找到全部，而是找到所有元素都在输入上的任何子集。

Answer 1

我认为跟踪每个子集中的剩余元素是正确的，但是您可以通过创建子集树来进行优化。

假设 N=10，并且您有子集 {1,2,3}、{1,2,4} 和许多其他子集。

找到在较大子集中最常一起出现的 2 个元素，然后为它们的组合创建一个新元素（如果这样的子集尚不存在）。例如，我们会说 10={1,2}，现在我们的原始子集是 {10,3} 和 {10,4}。

继续此过程，直到所有子集都达到大小 <= 2.

现在您可以使用原来的标记/计数过程，只不过当找到子集时，您需要查看它是否是任何其他集合中的元素并也标记这些集合。

我还没有准确地弄清楚如何评估此优化将提供的最坏或平均情况下的改进，但在实践中，您最终不太可能得到在大部分子集中使用的元素。

既然你的子集是固定的，你可以尝试一下，看看效果如何。