algorithm - 通用子集算法问题

Question

我有以下问题。

我有一组项目 {a1, a2, a3, ... aN}。这些项目中的每一个都可以包含另一组项目 {b1, b2, b3, ... bN}。所以最终结果看起来像这样:

a1
  b4
  b22
  b40
  b11
  b9
a2
  b30
  b23
  b9
  b4
  b11
a3
  b22
  b4
  b60
  b9

作为算法执行的结果，我想获得符合以下规则的 b 型对象组:

1. 如果一个a类对象下的多个b类对象仅存在于该a类对象下，则应将它们分组。
2. 如果在不止一个 a 类对象中使用了一个以上的 b 类对象，它们也应该被分组。

示例:

b4, b9
b30, b23

b40, b60, b11 and b22 shouldn't be grouped because there are no pairs for them.

我会用 C# 编写这个算法的实现，所以最好避免其中不存在的数据结构，例如二叉树、链表等。但这不是必需的；所有这些也都可以实现。

说明:集合可以包含所需数量的对象，但每个对象不超过 1 个。规则是同一a型中所有唯一的b型对象应该被分组(超过1个)，如果超过1个b型对象落在超过1个a型对象中，它们应该被分组。组应尽可能大。

现实生活中的例子:网页是a-type，这些页面上使用的CSS文件是b-type。为了加快页面的加载速度，你希望尽可能少的请求到服务器，所以你合并了CSS文件，但你不想合并自己只在少数页面上使用的文件，因为它们将被缓存，您不必再次重新下载它们。

Answer 1

首先，创建一个映射，将每个 b 类项目与包含该 b 类项目的 a 类项目集相关联。

在您的示例中，您将获得:

b4: { a1, a2, a3 }

b9: { a1, a2, a3 }

b11: { a1, a2 }

b22: { a1, a3 }

b23:{a2}

b30: {a2}

b40:{a1}

b60: {a3}

创建这个map，扫描a-type对象中的所有b-type对象，如果b-type对象没有关联，就在map中为它创建一个entry；但是，将 a 型对象添加到与 b 型对象关联的集合中。

然后，比较每对可能的集合 (O(n2))。如果两个 b 型对象具有相同的 a 型对象集，则将它们合并。

它在 map 上实现为一对嵌套循环(I=1 TO N-1，J=N+1 TO N)。

要比较两个集合，请使用集合库及其比较运算符。

如果 a 型对象可以用小整数表示，则可以将集合表示为位数组，这样比较紧凑且快速。