5

我有两个集合（它们恰好是数组，但我认为这并不重要）：L和R. 它们都已排序，现在我想比较它们。我想最终得到两个集合：一个用于每个输入数组，其中包含不在另一个集合中的项目。

我可以从中取出第一项L，然后进行搜索R，如果没有匹配项，则将其添加到我的“唯一”集合（Lu）中。但这是非常低效的，我希望在不久的将来处理一些非常大的集合。

我想可能“玩跳房子”：

  • 第 1 步：取两个列表L和R，并比较每个列表的头部 (l :: L和r :: R)：

    • 分支 1：如果l< r，则添加l和Lu递归，传入L和r :: R

    • 分支 2：如果l> r，则添加r和Ru递归，传入l :: L和R

    • 分支 3：如果l= r，则递归，传入L和R

  • 第 2 步：返回Lu并Ru

我可以编写这个函数，但在我付出努力之前，我想知道是否已经存在一个可以为我做这件事的函数。这似乎是一个不常见的场景，我总是宁愿使用现有的解决方案来滚动自己的解决方案。

（另外，如果这个算法有一个更容易识别的名字，我想知道它叫什么。）

4

1 回答 1

9

（我在大约2小时前写了上面的问题。从那以后，我自己找到了答案。以下是我发现的。）

在集合论中，L 中而不是 R 中的项目的“列表”称为“R 在 L 中的相对补集”，也称为“L 和 R 的集合论差异”

（参见维基百科的补充（集合论）文章）

F#，作为一种数学语言，将这个概念直接融入了它的核心库。首先，您需要将集合构建为集合：

// example arrays:
let arr1 = [| 1; 2; 3 |]
let arr2 = [| 2; 3; 4 |]

// build the L and R sets
let L = set arr1
let R = set arr2

现在您可以调用“差异”函数并快速获取每个数组的相对补码：

let Lu = Set.difference L R |> Set.toArray
let Ru = Set.difference R L |> Set.toArray

> val Lu : int [] = [|1|]
> val Ru : int [] = [|4|]

还有一个更短的语法。Set 类型重载了减号运算符。Set.difference只需从第一个参数中减去第二个参数，因此您实际上可以使用以下内容：

let Lu = L - R |> Set.toArray
let Ru = R - L |> Set.toArray

> val Lu : int [] = [|1|]
> val Ru : int [] = [|4|]
于 2014-01-27T19:21:27.167 回答