比较每个中唯一项目的两个列表

Question

我有两个集合(它们恰好是数组,但我认为它并不重要):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:if l= r,然后递归,传入L和R

• 第2步:返回Lu和Ru

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

(另外,如果这个算法有一个更易识别的名称,我想知道它叫什么.)

Answer 1

(我在大约2小时前写过上面的问题.从那以后,我自己找到了答案.以下是我发现的.)

在集合论中,L中但不在R中的项目的"列表"被称为"L中的R的相对补集",也称为"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|]