算法：检查集合包含的最快方法是什么？
拥有一个包含 N 个集合的数组，生成这些集合的包含图的最快方法是什么？
Having an array of N sets, what is the fastest way to generate the inclusion graph of these sets?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
如果您有一组 N 个集合，其中每个集合都不包含另一个集合，并且大小都相同，则您将需要进行 N^2 集合比较。
If you have a set of N sets none of which contain another, all of the same size, you are going to need to do N^2 set comparisons.
好吧，让我们从最坏的情况来推理，为了简单起见，假设您有一个有效的集合表示，您可以在恒定时间内检查成员资格。
要确定一组 X 是否是 Y 的子集，您必须执行 |X| Y 上的隶属度测试数量。所需时间与 |X| 成线性比例。
因此，如果你有 N 个集合，并且想要找出哪些集合是哪些其他集合的子集，则必须进行 N2 这样的子集测试，因此我认为最终的复杂度为O(AN2) 其中 A 是最大集合中的元素数量。
即使你可以做一些聪明的事情来同时决定“X子集Y”和“Y子集X”，你所获得的收益也不会超过2倍，因此复杂性不会提高。
Well, let's reason about it in terms of worst case, and for the sake of simplicity assume that you have an efficient set representation, in which you can check for membership in constant time.
To determine if one set X is a subset of Y, you have to do |X| number of membership tests on Y. Takes time linearly proportional to |X|.
So if you have N sets, and want to figure out which sets are subset of which other sets, you would have to do N2 such subset-tests, thus I suppose you end up with a complexity of O(AN2) where A is the number of elements in the largest set.
Even if you could do something smart to decide "X subset Y" and "Y subset X" at the same time, you wouldn't gain more than a factor 2, so the complexity would not improve.
首先，您可以证明，在给定 n 个集合的情况下，该图将包含 O(n^2) 条边：考虑集合 A1, ..., An，其中每个 Ak = {1, ..., k}。那么A1子集A2，A1子集A3，...，A1子集An，A2子集A3，...，即包含图中的n(n-1)/2条边。
鉴于此，我可以想到一个相当简单的方法来解决这个问题。设 Ai 可能是 Aj 的子集，当且仅当 Aj 中有某个 x 不在 Ai 中。现在，Ai 子集 Aj 当且仅当 Ai 可能是 Aj 的子集，而不是 Aj 可能是 Ai 的子集。
现在，对于每个元素 x 将您的集合分为两部分：包含 x 的集合和不包含 x 的集合。后者可能是前者的子集。将相应的边添加到可能子集图中。每当我们有一对在每个方向上连接的顶点时，我们就知道两个顶点都不是另一个顶点的子集。对于 m 个元素和 n 个集合的宇宙，该算法的复杂度为 O(mn^2)。
等等瞧！
First off, you can show that this graph will contain O(n^2) edges given n sets: consider sets A1, ..., An with each Ak = {1, ..., k}. Then A1 subset A2, A1 subset A3, ..., A1 subset An, A2 subset A3, ..., which is n(n-1)/2 edges in the inclusion graph.
Given that, I can think of a reasonably simple way to tackle this problem. Let Ai maybe-subset Aj iff there is some x in Aj which is not in Ai. Now, Ai subset Aj iff Ai maybe-subset Aj and not Aj maybe-subset Ai.
Now, for each element x divide your sets into two: those that contain x and those that don't. The latter maybe-subset the former. Add the corresponding edges to the maybe-subset graph. Whenever we have a pair of vertices connected in each direction, we know neither vertex is a subset of the other. This algorithm is O(mn^2) for a universe of m elements and n sets.
Et voila!
使用归并排序。
您的输出是包含（行，列）的 MxM 矩阵。这被初始化为全 TRUE。这是您的算法：
如果所有集合都是空的，则您有一个 MxM 集合
Use merge sort.
Your output is an MxM matrix of includes(Row, Column). This is initialized to all TRUE. Here is your algorithm:
If all the sets are empty you have a MxM set of