通用子集算法问题

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），并且如果多于一个b类型的对象属于多于1个a类型的对象，它们应该被分组。这些团体应该尽可能大。

活生生的例子：网站页面A型并在这些网页中使用的CSS文件b型。为了加快页面的加载速度，你希望有尽可能少的请求到达服务器，所以你结合了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}

要创建该图，在一个类型的对象扫描所有的B型的对象，并且如果b型对象没有关联，在地图上为它创建一个条目;但是将a型对象添加到与b型对象关联的集合中。

然后，比较每对可能的集合（O（n2））。如果两个b型对象具有相同的一组a型对象，则合并两个b型对象。

它被实现为映射上的一对嵌套循环（I = 1到N-1，J = N + 1到N）。

要比较两组，请使用set库及其比较运算符。

如果a型对象可能由小整数表示，那么可以将该集表示为位数组，它比较紧凑且快速。