问题标签 [set-intersection]

假设我有一个向量向量：

现在，在我的程序中，该向量包含在图中创建循环的节点组。如果它们相交，它们将创建强连通分量。

我需要遍历这个向量并有效地找到那些相交的向量，然后加入这些向量。可以通过蛮力 set_intersection 和 set_union 使用集合来完成，但它会很慢。

例如，如果我有简单 int 元素的向量 AD，其中 A、B、D 相交。

我想要这个结果：

现在，我在过去的几个小时里尝试了很多事情，但是简单的谷歌搜索表明 set_intersection 方法会很慢，我必须多次循环所有节点集（我认为它会是 N*(N + 1) /2，所以 O(N ² ) 没有启发式）。

我需要有效地做到这一点，所以我想到的是遍历所有节点并记下我找到原始节点的位置，然后在一次搜索中将它们组合在一起，如果可能的话。但是，我无法找到也无法设计出足够有效的算法，因此我将不胜感激有关如何解决此问题的一些帮助或想法。

谢谢你。

我有两个数组

和

我想从 A 中减去 B 并获得 A 中存在于 B 中的元素的索引。我该如何做到这一点？在这个例子中，我需要这样的答案：

几个常用的命令，如非零、删除、过滤器等，似乎无法用于 ND 阵列。有人可以帮我吗？

给定 2 个集合 (C++) 是否有一种方便的方法可以在没有任何分配的情况下获取交叉点的大小（如 std::set_intersection 所做的那样）

当然，我可以复制实现减去分配，但我总是宁愿不重新发明轮子

我正在考虑使用 std::set_intersection 并传递一个“计数”插入器......？

我正在寻找许多关于如何在有效时间内获得 2 组交集的查询。并寻找非常有效的方法。在采用我自己的方式之前，为什么不能要求 Java 构建一个方法来执行相同的操作。为什么 Java 没有在 Collections 类（如 sort 方法或 Collections 中的某个位置）上构建类似交集的方法？这背后有什么原因吗？

请考虑这是关于集合上相交的拟合下降的讨论。

谢谢，

我有一个问题需要解决，这有点简单，但我无法解决。任何帮助深表感谢。

好的。我有一百万条记录的数据集：

Origin 有 2 个选项：[Credit, Current]

现在，我需要过滤到那些 PersonGUID 在 Credit 和 Current 中至少有 1 行的交易。

我可以在 PythonPandas 中轻松完成此操作并加载 CSV，但我不想要 2 个数据集，因为我将围绕所有数据构建仪表板。

我猜是布尔逻辑计算字段，但我无法解决。

谢谢

抢

我一直在使用高度简洁和直观的 C​​++ 语法来查找两个 sortedvector的交集并将结果放在第三个中vector：

这应该设置c为 intersection( a, b)，假设a和b已排序。

但是如果我只是使用c.begin()（我以为我在某个地方看到了一个例子，这就是我这样做的原因）：

set_intersection期望OutputIterator在那个参数。我相信的标准只需要c.begin()返回 a forward iterator，我认为它可能是也可能不是OutputIterator。

无论如何，c.begin()在clang下编译的代码。

在标准下保证会发生什么？如果这样编译，可能会发生什么 - 也就是说，当返回的迭代器c.begin()最终递增超过向量的末尾，并尝试访问指向的元素时，必须/可能发生什么？在这种情况下，一个符合要求的实现可以默默地扩展向量，所以这begin()实际上是一个附加的事情OutputIterator吗back_inserter？

我问这个主要是为了了解标准如何与迭代器一起工作：真正发生了什么，所以我可以在使用 STL 时超越复制和粘贴。

如果我有可变数量的集合（我们称之为数字n），每个集合最多有m个元素，那么计算所有集合对的成对交集的最有效方法是什么？请注意，这与所有n 个集合的交集不同。

例如，如果我有以下集合：

我希望能够找到：

另一种可接受的格式（如果它使事情变得更容易的话）是给定集合中的项目到包含相同项目的集合的映射。例如：

我知道这样做的一种方法是创建一个字典，将所有n 个集合的并集中的每个值映射到它出现的集合列表，然后遍历所有这些值以创建intersections_C如上所述的列表，但是我不确定随着n的增加和集合的大小变得太大，它是如何扩展的。

一些额外的背景信息：

1. 每个集合的长度大致相同，但也非常大（足够大，以至于将它们全部存储在内存中是一个现实的问题，并且避免这种情况的算法将是首选但不是必需的）
2. 与集合本身的大小相比，任何两个集合之间的交集的大小都非常小
3. 如果它有帮助，我们可以假设我们需要对输入集的排序做任何事情。

我正在尝试对整数进行大量简单的“交集”操作。不幸的是，我在设置中没有可用的 numpy/scipy，我无法更改它。

我在 stackoverflow 上注意到 Python 集合操作很好地对数据进行了排序，这不仅加快了案例的加载速度，而且在我的情况下，我实际上也想对数据进行排序，因此这将是一个很棒的奖励。

我现在只是害怕它并不总是有效，所以我去测试：

结果是所有样本都被排序（没有打印错误的案例）。

虽然这很有说服力，但我想知道在使用集合交集时是否会出现整数未完全排序的情况？

我有一个集合列表：

我想要一组的全方位比较，即 2^n 组数：

在 Java 中执行此操作的最佳方法是什么？

例如，如果我只使用 5 套。我希望能够填充5 圈维恩图的所有重叠部分。

我正在尝试使用一组列表来做到这一点：

我想找到一些结果，例如：

本质上，我要问的是如何应用与集合并集相结合的powerset 算法。

有谁知道有效处理以下问题的特定数据结构/算法：

给定一个集合A和一组集合，S = {X,Y,Z..}我想计算 A 和 S 中的所有集合之间的交集的大小，利用它们中的大多数是非不相交的事实，即共享数。

例如：给定A = {1,2...10},X = {1,3,4,5,7}和Y = {2,4,5,7,9,10}, 计算A和X intersect Y,A和X - X intersect Y, Aand之间的交集Y - X intersect Y和对结果求和会更有效。

一个实际的例子可能是在共享一段文本的大量文档中查找关键字的出现次数，（不是总数，而是每个文档。）

请注意，与 Map-Reduce 的唯一区别是文档共享部分文本，并且这些部分应该只解析一次。

如果这有任何帮助，我现在对问题的推理方式是一个图/树，其中节点是重叠区域，其O(n)遍历给出了 A 和 S 的所有元素之间的交集大小。我面临的问题是如何找到要使用的最佳节点集。但也许已经有现成的解决方案了。