问题标签 [disjoint-union]

我有两组（IList），我需要第一个列表中的所有项目，其中项目不在第二个列表中。

谁能指出我用 LINQ 语句实现这一目标的最佳方法？

我在让查询工作时遇到问题，我认为这应该工作。它的形式

但是 mysql 在 "IN (" 开始的地方阻塞。mysql 是否支持这种语法？如果不支持，我该如何获得这些结果？我想在表 1 中找到不存在的 (a,b,c) 的不同元组在表 2 中。

今天，由于这张幻灯片的第 13 页，我与某人讨论了 Kruskal 最小生成树算法。

该演示文稿的作者说，如果我们使用（双）链表实现不相交集，则性能为Make和Find的性能将分别为O(1)和O(1)。运算Union(u,v)的时间为min(nu,nv)，其中nu和nv是存储 u 和 v 的集合的大小。

我说过我们可以通过使每个成员的表示指针指向一个包含指向集合的真实表示的指针的定位器来将Union(u,v)的时间缩短为O(1) 。

在 Java 中，数据结构如下所示：

对不起，简约的代码。如果可以这样制作，那么每个不相交集操作（Make,Find,Union）的运行时间将是O(1)。但与我讨论过的人看不到改进。我想知道你对此的看法。

Find/Union 在各种实现中的最快性能是什么？我不是数据结构方面的专家，但是通过在互联网上快速浏览，我发现没有恒定时间数据结构或算法可以做到这一点。

我有一个看似相对简单的 AND/OR 子句，这让我有点头疼。

我需要它来从$region和检索值$countries。但是，它的方式只返回 的值$countries。如果我删除带有它的行，OR它会返回 的值$region，但不会同时返回两者。我做错了什么？

在不相交的联合中，假设我们必须合并两棵高度分别为 h1 和 h2 的树。使用这种技术，如果 h1 不等于 h2，则结果合并树的高度将为 max(h1, h2)，如果 h1 == h2，则为 h1+1。在从初始情况开始的任意序列合并操作之后使用此技术，包含“k”个节点的树最多具有高度（logk 的地板）。这通过归纳证明如下。

基数：当 k=1 时，高度为 0. 0<= (floor(log 1))

归纳步骤：考虑k >1并通过假设定理对所有 m 都为真，使得1<=m<k。k可以通过合并两个较小的子树来获得包含节点的树。假设这两个较小的树分别包含“a”和“b”节点，我们可以在不失一般性的情况下假设a<=b。现在a>=1，因此没有办法从初始情况开始获得具有零节点的树，并且 k=a+b。它遵循a<=k/2and b<=k+1, since k>1, bothk/2 < k和(k-1) < kand 因此a<k, and b<k。

我上面的问题是

1. 我们如何得到上面的“它遵循 a<=k/2 和 b<=k+1”语句。

谢谢！

我有一个返回整数值或整数范围（initial..final）的方法，我想知道值是否都是不相交的。

有没有比以下更有效的解决方案：

嗨，这是我第一次在这里发帖，

我一直在尝试解决一个学习问题，但无法弄清楚：

我们考虑不相交集抽象数据类型的森林实现，按大小加权联合和路径压缩。最初，每个元素都位于单节点树中。

从上述初始状态开始：

1. 给出一个（短）UNION 和 FIND 操作序列，其中最后一个操作是一个 UNION，它导致较高的树 A 成为较短树 B 的子树（即 A 的高度严格大于 B 的高度） .

2. 显示最后一个 UNION 合并的两棵树 A 和 B

提示：您可以从 n = 9 个元素开始，每个元素都位于单节点树中。

我不确定这将如何工作，因为较小的树总是与较大的树合并，因为按大小联合？

谢谢。

首先，关于这个问题的一些背景：

我正在一个具有多种类型资源（A、B、C ...）的系统中工作。我有一些资源需求，我需要确定我是否能负担得起。

为此，我有一些资源，每个资源都可以提供不止一种类型的资源，但我需要为每种资源选择我要使用的资源。

例如，如果我需要支付 1A、2B 和 0C（表示为 (1,2,0)）并且我有这个来源：

1. (1,1,0) //意味着我必须选择生产 A 或 B
2. (0,1,1) //意味着我必须选择生产 B 或 C
3. (1,1,0)

很明显，我必须将源 2 用于资源 B，我可以选择 1 和 3，其中一个产生 A 和 B

我实现这一点的方法是将其视为一个依赖关系图，其中上述情况表示如下：

因此，我遍历资源，并且对于每个资源，我都会遍历到达它的链接。如果删除当前资源的当前节点意味着其他资源有足够的剩余到达链接来支付剩余的费用，我使用它。

对于前面的示例，我首先尝试将源 1 用于资源 A。B 仍然有 2 个链接，所以我可以做到。只剩下 B 类资源需要支付，所以我使用剩余资源支付 B。

好的，但现在我需要在一个新场景中工作，其中有两种类型的资源，每一种以成本 1 或成本 2 生产一种资源，我需要最小化总成本。

对示例的轻微更改可能是这样的：

常识解决方案应该是使用1和2支付B，使用3支付A，总成本为1，但在我的实现中，如上所述，源1用于支付A，因为B还有2个链接到它，所以最后我必须使用成本为 2 的源 3。

如果可能，应避免暗示尝试所有选择组合的解决方案。

您是否知道可以应用于这种情况的任何具有已知解决方案的一般算法问题？或者如何改进我的实际解决方案以在这个新场景中工作？还是我应该采取另一种不同的方法？

如何使用不相交的森林来安排带有惩罚的作业，从而将惩罚降到最低？

我们可以首先根据他们的惩罚程度将工作按降序排列。森林的每个节点 x 将代表作业编号，值 rank[x] 将代表其惩罚。但是我怎样才能最小化这个值 rank[x] 以便最小化惩罚？节点的顺序会给我作业的顺序，但是这个算法是什么？我该如何去造林？

是否在某个库中实现了可变参数计数 scala Either，我的意思是类似于HList. 我不想自己实现它:-)