查找公共(public)子集的算法

Question

我有 N 组 S_i 个数字，每个都有不同的大小。让m₁, m₂, ... m_n 是各个集合的大小 (m_i = | S_i |)，并且 M是最大集合的大小。我必须找到其中至少有两个数字的公共(public)子集。示例:

Set  Items
1    10,80,22
2    72, 10, 80, 26,50
3    80,
4    10, 22
5    22, 72, 10, 80, 26,50

所以结果会是这样

Items                Found in sets
10, 22               1, 4
10, 80               1, 2, 5
10, 80, 22           1, 5
10, 72, 80, 26, 50   2, 5

那么如何自动解决这个问题以及相应解决方案的预期复杂度是多少？我需要它尽可能快。

Answer 1

由于原始问题要求尽可能快地进行讨论，因此可以通过以下方式缩短讨论时间。

首先，讨论输出是否与您的输入成指数关系。假设您有 2 个元素和 N 个集合。假设每个元素属于每个集合；它将需要 N 行作为您的输入。那么，你应该打印多少行？

我认为您将打印 2^N-N-1 行，如下所示:

1,2     1,2
1,2     1,3
.....
1,2     1,N
1,2     2,1
.....
1,2     1,2,3
.....
1,2     1,2,3,...N

由于您将花费 O(2^N) 时间打印，您可以选择此页面上的任何建议来计算此信息 — 无论如何您已经被指数捕获了。

这个论点会让你们的讨论变得非常快。