程序员经验分享-hwhale

n 个集合的所有组合的交集

2024-02-21

我需要帮助找到一种有效的算法来解决这个问题：

Given n未排序的整数集，找到所有可能的组合n以及它们的交集。例如：

Input (n=3):

Set 1 = 1, 10, 6, 11, 14, 3
Set 2 = 3, 7, 11, 9, 5
Set 3 = 11, 6, 9, 1, 4

Output:

Set 1 & 2: 3, 11
Set 1 & 3: 1, 6, 11
Set 2 & 3: 9, 11
Set 1, 2, & 3: 11

我正在考虑首先找到集合的所有可能组合，然后使用算法来找到集合的交集n在这里找到的集合：交集n sets http://www.geeksforgeeks.org/intersection-of-n-sets/。不过，我担心这种方法的时间效率。

如果您能找到比我幼稚的方法更好的方法，那么伪代码的答案将是最有帮助的。


这是一个受启发的解决方案MapReduce：简化大型集群上的数据处理 http://research.google.com/archive/mapreduce.html，因此如果您愿意，可以以分布式方式编写。

将集合中的所有元素映射为对[element, set]。按元素对该列表进行分组。您只需排序并提取元素即可。或者，您可以创建数组的哈希值，其键是元素，值是在其中找到该元素的集合列表。然后对于每个元素，发出一个列表[combination of sets, element]。通过组合对其进行分组。现在，对于每个非空组合，您只需读取其中的元素即可。

如果你想用真实的分布计算映射减少，第一个映射将映射到元素的键和集合的值。第一个reduce只会按元素存储它所在的集合列表。第二个map将为每个元素发出它所在的每个集合组合的一个键，并以元素作为值。第二次减少将存储您的最终答案。

详细说明您的示例可能会有所帮助。你从以下开始：

Set 1 = 1, 10, 6, 11, 14, 3
Set 2 = 3, 7, 11, 9, 5
Set 3 = 11, 6, 9, 1, 4

您将其映射到列表：

[1, Set 1], [10, Set 1], [6, Set 1], [11, Set 1], [14, Set 1], [3, Set 1],
[3, Set 2], [7, Set 2], [11, Set 2], [9, Set 2], [5, Set 2],
[11, Set 3], [6, Set 3], [9, Set 3], [1, Set 3], [4, Set 3],

现在按元素分组（我通过排序手动完成）以获得：

1: Set 1, Set 3
3: Set 1, Set 2
4: Set 3
5: Set 2
6: Set 1, Set 3
7: Set 2
9: Set 2, Set 3
10: Set 1
11: Set 1, Set 2, Set 3
14: Set 1

现在我们进行第二次映射（跳过仅在一组中的元素）以获得：

[(Set 1, Set 3), 1],
[(Set 1, Set 2), 3],
[(Set 1, Set 3), 6],
[(Set 2, Set 3), 9],
[(Set 1, Set 2), 11],
[(Set 1, Set 3), 11],
[(Set 2, Set 3), 11],
[(Set 1, Set 2, Set 3), 11]

通过集合的组合对其进行分组，我们得到：

(Set 1, Set 2): 3, 11
(Set 1, Set 3): 1, 6, 11
(Set 2, Set 3): 9, 11
(Set 1, Set 2, Set 3): 11
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

Algorithm

datastructures

set

bigo

combinations

n 个集合的所有组合的交集 的相关文章

  • 根据多个值过滤字典列表

    我有一个字典列表 我想根据多个条件进行过滤 该列表的简化版本如下所示 orders name v price 123 location Mars name x price 223 location Mars name x price 124

  • 当目标是查找某个字符串的所有出现情况时，KMP 最坏情况的复杂度是多少？

    我还想知道哪种算法在查找另一个字符串中所有出现的字符串时具有最坏情况的复杂性 博耶 摩尔算法似乎具有线性时间复杂度 KMP 算法在查找字符串中所有出现的模式时具有线性复杂度 如 Boyer Moore 算法1 如果您尝试在 aaaaaaaa

  • 如何使用KDTrees实现最近邻搜索？

    所以 我正在实施一个KD Tree http en wikipedia org wiki Kd tree进行最近邻搜索 我已经构建了树部分 但我认为我没有完全理解搜索部分 关于遍历树来搜索邻居 维基百科文章如下 Starting with

  • 如何在Scala中实现尾递归快速排序

    我写了一个递归版本 def quickSort T xs List T p T T gt Boolean List T xs match case Nil gt Nil case gt val x xs head val left righ

  • 反转二进制网络

    如何反转二元方程 以便找到哪些输入将产生给定的输出 Example Inputs i0 through i8 Outputs o0 through o8 Operators XOR AND 二元方程 1 i0 1 i1 0 i2 1 i3

  • 初始化 HashMap 的最佳方法

    我通常会这样做 HashMap

  • Java：如何实现3和？

    我正在研究 3 Sum 来自己实现它 并遇到了以下规则的实现 给定一个由 n 个整数组成的数组 S S 中是否存在满足 a b c 0 的元素 a b c 查找数组中所有总和为零的唯一三元组 注意 三元组 a b c 中的元素必须按非降序排

  • 基于时间的算法评分

    我们希望创建一种评分算法 在更短的时间内获得更高的分数 在更长的时间内获得更少的分数 需要注意的是 没有实际范围 因此时间范围可以从 100 毫秒到长达 10 分钟或更长时间 点范围为 0 到 50 谢谢你的帮助 你可以简单地把它变成一个线

  • 如何从二叉搜索树中均匀随机地返回节点？

    给定一个 BST 可能平衡也可能不平衡 如何能够均匀地随机返回 任何 节点 一个限制是您不能使用外部索引数据结构 您必须以每个节点都有平等被访问的机会的方式遍历树 这个问题让我困惑了好一阵子 如果我们确实可以使用外部哈希表 指针 我们可以对

  • 搜索/排序算法 - 是否有类似 GoF 的列表？

    我是一名自学成才的开发人员 坦率地说 我不太擅长找出在任何特定情况下使用哪种搜索或排序算法 我只是想知道是否有设计模式 esque 列出了以太坊中可用的常见算法 供我添加书签 就像是 算法名称 带有别名 如果有的话 它解决的问题 大O成本

  • 用 Java 创建迷宫求解算法

    我被分配了用 Java 创建迷宫求解器的任务 这是任务 Write an application that finds a path through a maze The maze should be read from a file A

  • 使到 n 个点的集合的欧氏距离之和最小的点

    我有一组点W x1 y1 x2 y2 xn yn 在 2D 平面上 你能找到一种算法 将这些点作为输入并返回一个点 x y 在 2D 平面上 距以下点的距离之和最小W 换句话说 如果 di Euclidean distance x y xi

  • Exposé 布局算法

    我正在制作一些项目 其布局类似于 Mac OS X 在 Expos 中对窗口所做的操作 它适应项目的长宽比和可用区域的长宽比 基本上 可用区域分为行和列 每个单元格 行和列的交集 中放置一个项目 这些项目必须保持其纵横比 此处width h

  • 缩短文本并仅保留重要句子

    德国网站 nandoo net 提供了缩短新闻文章的可能性 如果使用滑块更改百分比值 文本会发生变化并且某些句子会被遗漏 您可以在这里看到它的实际效果 http www nandoo net read article 299925 http

  • 如何在给定目标索引数组的情况下对数组进行就地排序？

    你如何对给定的数组进行排序arr in place给定目标索引数组ind 例如 var arr A B C D E F var ind 4 0 5 2 1 3 rearrange arr ind console log arr gt B E

  • 节点*链表中的下一个

    我是数据结构和算法的新手 我遇到了以下代码 typedef struct node int data node next 谁能告诉我为什么我们要声明节点 next next 不能声明为 int next 吗 因为你希望能够做到n gt ne

  • 使用C标准数学库精确计算标准正态分布的CDF

    标准 C 数学库不提供计算标准正态分布 CDF 的函数 normcdf 然而 它确实提供了密切相关的函数 误差函数 erf 和互补误差函数 erfc 计算 CDF 的最快方法通常是通过误差函数 使用预定义常量 M SQRT1 2 来表示 d

  • Ruby 中的 Set 是否始终保留插入顺序？

    即 Ruby 的 Set 相当于 Java 的 LinkedHashSet 吗 在 Ruby 1 9 中 yes 在 Ruby 1 8 中 可能不会 Set uses a Hash内部 https github com ruby ruby

  • Codility 钉板

    尝试了解 Codility NailingPlanks 的解决方案 问题链接 https app codility com programmers lessons 14 binary search algorithm nailing pla

  • 如何从一组重叠的圆计算多边形集？

    这个问题是一些计算细节的扩展这个问题 https stackoverflow com questions 1667310 combined area of overlapping circles 假设有一组 可能重叠的 圆 并且希望计算这组

随机推荐

  • Html2Pdf -Codeigniter -图像未加载

    我正在使用 HTML2PDF 库作为 codeigniter See https github com aiwmedia HTML2PDF CI https github com aiwmedia HTML2PDF CI我的问题是我无法使用

  • 使用 Unity 新输入系统的多个控制器

    我正在尝试将新的 Unity 输入系统与多个控制器一起使用 我尝试为每个角色创建输入操作 但这不起作用 所有角色同时移动 看起来角色并不关心控制器 而是关心输入 而不管控制器如何 也许我需要等待输入系统的最终版本 但是 我真的不想使用旧系统

  • 将微调器添加到 ActionBar（而不是导航

    我使用答案中的第二个选项向我的 ActionBar 添加了一个微调器here https stackoverflow com questions 8312344 how to add a dropdown item on the actio

  • Visual Studio - 如何使用相同的源创建两个项目

    我的解决方案由 2 个可执行项目和几个 dll 组成 Project1 是智能设备项目 Project2 是 Windows 窗体项目 这两个项目都使用相同的库 原因是我想在将库部署到设备上之前在 PC 上测试它 问题是 DLL 项目类型可

  • 延迟作业和 Mandrill：未初始化常量 Mandrill::API

    我有邮件服务 用户可以上传包含电子邮件和其他一些用户相关数据的 xls 文件来发送电子邮件活动 我遇到了一些超时问题 因为它需要几秒钟的时间来处理 因为我对每封要发送的电子邮件进行了一些验证和配置 例如 将记录保存到数据库 检查过去 30

  • 文件类型的可可图标？

    如果我有一个文件 我可以通过执行以下操作来获取图标 NSImage iconImage NSWorkspace sharedWorkspace iconForFile myFile png 但如果我只是想获取特定文件类型的图标 例如与 pn

  • 在 Apple 平台的 AArch64 汇编中，如何在一行中编写多个语句？

    我正在将一些 Arm64 汇编语言移植到 M1 其中一些是由 C 预处理生成的 其中单个 define宏生成多个以分号分隔的语句 不幸的是 在 M1 上 汇编器将分号视为注释字符 例如 define DEFUN NAME globl NAM

  • 可选框架不起作用（CoreAudioKit 不在模拟器上）

    为了让 MIDI 通过蓝牙工作 我需要使用CoreAudioKit框架 这工作完美 但我无法在模拟器上编译 使框架 可选 没有帮助 错误是ld framework not found CoreAudioKit 我认为它应该按照the doc

  • Azure-Container-Service 中的安装卷不适用于 traefik.toml 和 /var/run/docker.sock

    构建从 VSTS 到 Azure container service 的 CI CD 管道 我在安装 traefik toml 和 docker sock 文件时遇到了问题 部署使用 SSH 隧道创建文件夹 Deploy 并复制 docke

  • C# 有异步函数调用同步函数或同步函数调用异步函数

    我正在编写一个 C Net 4 5 库 用于执行常见的 sql 数据库操作 备份 恢复 执行脚本等 我希望每个操作都具有同步和异步函数 因为控制台和 GUI 应用程序都将使用该库 但我不想到处重复代码 所以在我看来 我有两个选择 编写在同步

  • 使用 insertWithOnConflict 进行更新或插入

    我需要插入或更新 我找到了 SQLiteDatabase 的 insertWithOnConflict 方法 但我不知道它如何检查该条目是否已存在 理论上 我需要一个 Where 参数来检查某个 ID 是否存在 如果存在 它应该替换所有其他

  • .R中的第一个函数

    我不明白 R 中 First 函数的意义 我的原因是 Rprofile 中的任何代码都将在 R 启动时被获取并执行 this First lt function library devtools and this library devto

  • WordPress：如何按 ACF 自定义字段对内容进行排序？

    通过使用高级自定义字段插件 我创建了一个包含 6 种成员资格类型的选择下拉列表 我使用此自定义字段的所有 列表 都被分配为 6 个字段之一 我想通过以下方式显示所有 列表 终极加号最终的专业的商业的商业 Free 按照这个特定的顺序 那些支

  • 将 JavaScript 变量发送到 PHP 变量 [重复]

    这个问题在这里已经有答案了 首先我认为我必须将 JavaScript 转换为 PHP 但后来我发现我不能 因为服务器和客户端执行 所以现在我只想发送一个变量 到 PHP 变量 当我点击一个按钮时 JavaScript 中的该函数就会执行 现

  • Java 和 .Net 正则表达式

    Java 和 Net Framework 正则表达式模式之间的区别 我正在尝试转换我的 Net Framework 但模式无效 谁能指出正则表达式模式的主要区别 例如我们如何命名java中的分组结构等等 有很多差异总结在这里 http ww

  • 比较 C# 中的双精度值

    I ve a double变量称为x 在代码中 x被赋值为0 1我在 if 语句中检查它比较x and 0 1 if x 0 1 不幸的是它没有进入if陈述 我应该使用Double or double 这背后的原因是什么 您能为此建议一个解

  • Selenium - 无响应脚本错误 (Firefox)

    这个问题以前曾被问过 但给出的答案似乎对我不起作用 问题是 当使用 Selenium 打开页面时 我会收到许多 无响应脚本 弹出窗口 引用不同的脚本 当我使用不带 Selenium 的 Firefox 打开页面时 没有出现任何错误 另外 奇

  • 我可以通过编程方式设置 Mercurial 配置选项吗？

    我正在寻找一种设置方法 hgrc配置项 而无需实际编辑文本文件 我正在尝试标准化设置hgrc跨多个开发人员 我想要一个像这样的命令 hg config ui username foo 但这也将该配置更改保存到hgrc file 看起来这应该

  • 通过 javascript 添加的输入字段不在 PHP $_POST 变量中。如何解决这个问题？

    我在 html 表中有一个表单 我通过 jquery 动态地将输入字段添加到表单中 当我在提交表单时进行 var dump 时 POST 数组没有添加的字段 为什么会发生这种情况 这是我的 js 的样子 add more del areas

  • n 个集合的所有组合的交集

    我需要帮助找到一种有效的算法来解决这个问题 Given n未排序的整数集 找到所有可能的组合n以及它们的交集 例如 Input n 3 Set 1 1 10 6 11 14 3 Set 2 3 7 11 9 5 Set 3 11 6 9 1

热门标签