algorithm - 如何找到具有最多共同项的子集？

Question

假设我有许多“已知”集合:

1 {a, b, c, d, e}
2 {b, c, d, e}
3 {a, c, d}
4 {c, d}

我想要一个将集合作为输入的函数(例如 {a, c, d, e})并找到元素数量最多的集合，并且没有其他共同点。换句话说，具有最大基数的子集。答案不一定是适当的子集。这种情况下的答案是 {a, c, d}。

编辑:上面的例子是错误的，现在修正了。

我正在努力寻找绝对最有效的方法。

(在下面，为了简单起见，我假设比较两个集合的成本是 O(1)。该操作不在我的控制范围内，因此没有必要考虑它。事实上，它是被比较的两个集合的基数的函数。)

候选人 1:

生成输入的所有子集，然后迭代已知集并返回最大的一个子集。这样做的缺点是复杂度类似于 O(n! × m)，其中 n 是输入集的基数，m 是“已知”子集的数量。

候选人 1a(感谢@bratbrat):

遍历所有“已知”集并计算交集的基数，然后取值最高的那个。这将是 O(n)，其中 n 是子集的数量。

候选人2:

创建一个逆向表并计算输入和已知集之间的欧氏距离。这可能很快。我不清楚如何将其限制为仅包含没有后续 O(n) 过滤器的子集。

候选人 3:

遍历所有已知集并与输入进行比较。复杂度为 O(n)，其中 n 是已知集合的数量。

我可以随意使用 Python 和 Redis 中内置的 set 函数。

这些似乎都不是特别好。想法？集合的数量可能会变大(猜测大约 100,000)。

Answer 1

没有可能在不到 O(n) 的时间内完成此操作...仅读取输入是 O(n)。

几个想法:

按大小对集合进行排序(最大的在前)，并搜索作为输入集合的子集的第一个集合。一旦找到一个，就不必检查其余部分。

如果集合中可能的项目数量有限，您可以用位向量表示它们。然后你可以计算一个查找表来告诉你给定的集合是否是输入集合的子集。 (逐字逐句地查看每个正在考虑的输入集的位，将每个词索引到适当的表中。如果您找到一个条目，告诉您它不是一个子集，您可以再次直接移动到下一个输入集。 ) 这是否真的会给你带来性能，取决于实现语言。我认为它在具有原始整数类型的语言(如 C 或 Java)中最有效。