查找公共子集的算法

Question

我有N个数量的集合S _i,每个都有不同的大小.设m ₁,m ₂,... m _n为各组的大小(m _i = | S _i |),M为最大组的大小.我必须找到至少有两个数字的公共子集.例:

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 ) 时间打印，您可以选择此页面上的任何建议来计算此信息 - 无论如何，您已经被指数抓住了。

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

Answer 2

我有一些建议。当您循环计数该集合中的数字时，您应该对集合中的所有项目进行排序。您应该添加条件来检查数字是否大于您的搜索值并使用中断；循环结束。