通用子集算法问题
我有以下问题。
我有一组项目 {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 类型对象组：
- 如果 a 类型对象下有多个 b 类型对象仅存在于该 a 类型对象下，因此应将它们分组。
- 如果在多个 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 类型，这些页面上使用的CSS 文件是b 类型。为了加快页面的加载速度，你希望向服务器发出的请求尽可能少，因此你组合了CSS文件，但你不希望组合只在少数页面上自己使用的文件，因为它们将被缓存，您不必再次重新下载它们。
I have the following problem.
I've got a set of items {a1, a2, a3, ... aN}. Each one of those items can contain another set of items {b1, b2, b3, ... bN}. So the end result looks something like this:
a1
b4
b22
b40
b11
b9
a2
b30
b23
b9
b4
b11
a3
b22
b4
b60
b9
As a result of the execution of the algorithm I would like to get the groups of b-type objects that fall under following rules:
- If more than one b-type object under an a-type object only exists under that a-type object, they should be grouped.
- If more than one b-type object is used in more then one a-type object they also should be grouped.
Example:
b4, b9
b30, b23
b40, b60, b11 and b22 shouldn't be grouped because there are no pairs for them.
I would be writing the implementation of this algorithm in C#, so it would be nice to avoid data structures that don't exist in it, such as binary trees, linked lists, etc. But this is not a requirement; all of these could be implemented too.
Clarification: Sets can contain as many objects as needed, but not more than 1 of each. The rules are that all unique objects of b-type within the same a-type should be grouped (more than 1), and if more than 1 b-type object fall within more than 1 a-type object, they should be grouped. The groups should be as large as possible.
Real life example: Web-pages are a-type and the CSS files used on those pages are b-type. In order to speed up the loading of the pages, you want to have as few requests as possible going to the server, so you combine CSS files, but you don't want to combine files that are used by themselves only on a few pages, since they will be cached and you don't have to re-download them again.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（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 }
创建此映射时，会扫描 a 类型对象中的所有 b 类型对象，如果 b 类型对象没有关联，则在映射中为其创建一个条目；但是，将 a 类型对象添加到与 b 类型对象关联的集合中。
然后，比较每个可能的集合对 (O(n2))。如果两个 b 类型对象具有相同的 a 类型对象集，则合并它们。
它被实现为映射上的一对嵌套循环（I=1 TO N-1，J=N+1 TO N）。
要比较两个集合，请使用集合库及其比较运算符。
如果 a 类型对象可以用小整数表示，则可以将集合表示为位数组，这非常紧凑并且可以快速比较。
First, create a map that associates every b-type item with the set of the a-type items that contains that b-type item.
In your example, you'll get:
b4: { a1, a2, a3 }
b9: { a1, a2, a3 }
b11: { a1, a2 }
b22: { a1, a3 }
b23: { a2 }
b30: { a2 }
b40: { a1 }
b60: { a3 }
To create this map, scan all the b-type objects in the a-type objects, and if the b-type object has no association, create an entry in the map for it; however add the a-type object to the set associated to the b-type object.
Then, compare every possible pairs of sets (O(n2)). Merge two b-type objects if they have the same set of a-type objects.
It is implemented as a pair of nested loops over the map (I=1 TO N-1, J=N+1 TO N).
To compare two sets, use a set library and its comparison operator.
If the a-type objects may be represented by small integers, you can represent the set as a bit array, that is quite compact and quick to compare.