寻找共同子集的算法

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

那么如何自动化解决这个问题，各种解决方案的预期复杂度是多少？我需要尽可能快地完成。

- Ali

---

N和M可能会有多大？ - Will A

N可以是任何数字，但假设n = 100，m的最大值为15个项目。 - Ali

你的意思是在你的例子中，M 被认为是6吗？（仅限于一行中最大项数（即一个数组中的项数）） - nonopolarity

m可以有一个最大值吗？那么m维度确实可以是一个常数...即使它是15 * 15，它也是225，当考虑O()时被视为一个常数。 - nonopolarity

嗯，你需要尽可能快地进行讨论吗？ - P Shved

你的意思是要找到所有的配对还是只找一个配对？ - nonopolarity

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)时间进行打印，因此您可以选择本页上的任何建议来计算此信息 - 无论如何，您都被指数所限制。

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

- P Shved

---

不要忘记，所有这些I/O操作很可能比计算步骤的常数因子更高。很不错。 - jk.

这很有趣，但我相信Ali想让算法快速，而不是讨论。 :-) - paxdiablo

@pax，嗯，我不确定阿里想要如何让具有指数下界的算法快速运行。所以我假设这是关于讨论的。 - P Shved

谢谢Pavel Shved。我知道这个解决方案，但系统会陷入昏迷状态（它会休眠数年）。无论如何，感谢您的算法。 - Ali

Answer 2

我能想到的一种解决方案：

使用哈希表，生成该“行”中数字的“一对数字”的所有组合，时间复杂度为O（M * M）。

然后将这些组合作为哈希键，映射到主数组索引。

For each row of those N elements,
  do the step above... and if the hash already maps to a number, then it is a match,
    then return the pair, or else just put those in the hash

这是O(N * M * M)的时间复杂度。

更新：如果您在评论中所说的M最大可以为15，则O(N * M * M)实际上与O(N)相同。

---

如果您最初的问题是找到所有配对，则

For each row of those N elements,
  do the step first mentioned... and if the hash already maps to a number, 
    then it is a match and just print out the pair if this pair is not printed yet
  and in any event, put the mapping into the hash

to tell whether a pair has been printed, created another hash, such as
  printed_or_not[i,j] = true or false, 
    and make sure to check printed_or_not[i,j] or printed_or_not[j, i]
    because not need to print again if just different order

- nonopolarity

Answer 3

您可以这样做 -

1. 创建一个哈希表，并将每个项作为键插入，将它们所属的集合作为值。 例如：10:[0,1,3,4] 80:[0,1,2,4] 22:[0,3,4] 72:[1,4] 26:[1,4] 50:[1,4]

2. 然后对于哈希表中的每两个元素，找到键的值的交集。例如(10,80)的交集为[0,3,4]。对于(10,22)(10,72)等也是如此。这样就得到了结果。

3. 复杂度 - 将M个项插入哈希表 - O(M) 在哈希表中搜索每个键 - O(1) 键值的交集操作 - O(m^2) [这可以优化]

总体而言，我会说这是O(m^2)算法。但如果每个“集合”中的“项”的大小不大，则不会有太大的性能影响。

- Srikar Appalaraju

Answer 4

您被要求对您的所有集合进行成对交集，并收集所有大小大于等于2的结果。

有O(N^2)个成对，每个的交集都需要O(M)。收集所有结果，按设置内容排序以解决重复项为N^2 Log N^2（最坏情况是每个对的交集都不同，因此可能会产生O(N^2)个结果集）。

所以我认为复杂度是O((N^2 + N log N) * M)。

但是很可能出现错误。

保罗

- The Archetypal Paul

Answer 5

我有一些提示。当你在循环中计算一个集合中的数字时，你应该对其中的所有项目进行排序。你应该添加条件来检查一个数字是否大于你要搜索的值，并使用break;来结束循环。

- cloverink