范围交集/并集

Question

我正在开发一门编程语言，希望提供一个名为Range的数据类型。与通常不同的是，目前这个数据类型不是一个int值对(x,y)的列表，而是有限制条件x < y的值对列表。我之所以说与通常不同，是因为在我的情况下，一个范围不仅仅是一个值对，它可以是多于一个值对，例如：

1 to 5, 7 to 11, 13 to 22

所有内容都包含在一个对象中。

我想提供两个函数来生成两个范围的并集和交集，这些函数应该从一对范围中包含最少数量的非重叠区间。例如：

1 to 5 || 3 to 8 = 1 to 8
1 to 5 && 3 to 8 = 3 to 5
(1 to 3, 4 to 8) && 2 to 6 = (2 to 3, 4 to 6)

其中||代表并集，&&代表交集。

目前它们的实现只是一个列表，正如之前所述。我知道存在更适合的数据结构（区间树），但目前我更关心从其他列表的并集/交集中构建新列表。

哪些最先进的算法可用于实现这两个函数？

提前致谢。

- Jack

Answer 1

由于您不想处理区间树，只使用列表，我建议您将范围表示保持为按x坐标排序的不相交区间列表。

给定两个列表，您可以通过执行一种类似于合并排序列表的合并步骤来计算它们的并集和交集。

示例：

对于L1和L2的并集：

创建一个空列表L。

从L1和L2中获取具有最小x值的区间，并将其放入L中。

现在再次取最小值，与L的最后一个元素进行比较，并决定它们是否需要合并（如果重叠）或将新区间附加到L的末尾（如果它们不重叠），并继续处理，就像我们在合并两个排序列表中所做的那样。

完成后，L将是按x排序且不相交的区间的并集。

对于交集，您可以执行类似的操作。

- Aryabhatta

Answer 2

在我看来，存储区间的最佳方法 - 区间树 - 也是执行操作的手段。由于区间树查询支持点树交集是主要情况，因此扩展到区间-区间交集似乎并不太难：对于tree1中的每个区间，请查询tree2的两个端点。对于交集，从tree1中减去相交的区间，并对于联合，添加相交的区间。对于每个减法/加法操作，您将获得一组新的区间，可以添加到您的新tree3中，这将成为您操作的结果。

- codekaizen

Answer 3

没有区间树...... 不需要特殊排序...... 可能不是“最先进的技术” :)

        (* "{ ... }" means "list" *)

function Union [{x1_,x2_},{y1_,y2_}] := 

      if {x1,x2}=={} then {x1,x2}={y1,y2} (* This is needed because the intersection *)
      if {y1,y2}=={} then {y1,y2}={x1,x2} (* may return an empty interval *)
                                          (* so, empty intervals need this code *)

      if {y1,y2}=={} then return[{}]      (* Both intervals were empty! *)

      if Min[x1,x2] > Min[y1,y2] 
      then   
          return[Union[{y1,y2},{x1,x2}]] (* or swap intervals *)
      else
          If Max[x1,x2] < Min[y1,y2]
          then                       (* Non Overlapping*)
              return[{{x1,x2},{y1,y2}}]
          else                       (* Overlapping intervals *)
              return[{Min[x1,x2],Max[x1,x2,y1,y2]}]

end function <Union>                      

function Intersection  [{x1_,x2_},{y1_,y2_}] := 

      if ({x1,x2}=={} OR {y1,y2}=={}) then return[{}] (* empty intervals do exist *)

      if Min[x1,x2] > Min[y1,y2]
      then   
          return[Intersection[{y1,y2},{x1,x2}]] (* or swap intervals *)
      else
          If Max[x1,x2] < Min[y1,y2]
          then                       (* Non Overlapping*)

              return[{}]             (* HERE we create an empty interval*)

          else                       (* Overlapping intervals *)

              return[{Min[y1,y2],Min[Max[x1,x2],Max[y1,y2]]}]

end function <Intersection>

编辑>

或许将函数推广到n个参数比二元函数更好。

类似于>（对于非标准伪代码表示抱歉）

        function GenUnion[{L:list of intervals}]:=

                 if (Tail[L] is interval)
                     return[Union[Head[L],Tail[L]]]
                 else                                                            
                     return[Union[Head[L], GenUnion[Head[Tail[L]],Tail[Tail[L]]]  

        end function <GenUnion>

- Dr. belisarius

---

别担心，我正在使用OCaml，所以欢迎函数式代码 :) 我会查看你的建议。 - Jack

Answer 4

我将发布到目前为止的自己的实现（仅联合操作），我正在使用一种函数式语言，所以请注意..可能会有些混淆：

let rec calc c l1 l2 =
  match c,l1,l2 with                            
    None, (f1,t1) :: y1, ((f2,t2) :: y2 as n2) when f1 < f2 -> calc (Some (f1,t1)) y1 n2
    | None, n1, (f2,t2) :: y2 -> calc (Some (f2,t2)) n1 y2
    | None, _, _ -> []
    | (Some (fc,tc) as cur), (f1,t1) :: y1, ((f2,t2) :: y2 as n2) when t1 <= fc -> calc cur y1 n2
    | (Some (fc,tc) as cur), ((f1,t1) :: y1 as n1), (f2,t2) :: y2 when t2 <= fc -> calc cur n1 y2
    | Some (fc,tc), (f1,t1) :: y1, ((f2,t2) :: y2 as n2) when f1 <= tc && t1 > fc -> calc (Some (fc,t1)) y1 n2
    | Some (fc,tc), ((f1,t1) :: y1 as n1), (f2,t2) :: y2 when f2 <= tc && t2 > fc -> calc (Some (fc,t2)) n1 y2
    | Some (fc,tc), (f1,t1) :: y1, ((f2,t2) :: y2 as n2) when f1 < f2 -> [fc,tc] @ calc (Some (f1,t1)) y1 n2
    | Some (fc,tc), (t :: e as n1), (f2,t2) :: y2 -> [fc,tc] @ calc (Some (f2,t2)) n1 y2
    | Some (fc,tc), [], (f,t) :: tr when f <= tc && t > tc -> calc (Some (fc,t)) [] tr
    | Some (fc,tc), [], (f,t) :: tr when f <= tc && t <= tc -> calc (Some (fc,tc)) [] tr
    | Some (fc,tc), [], x -> [fc,tc] @ x
    | Some (fc,tc), (f,t) :: tr, [] when f <= tc && t > tc -> calc (Some (fc,t)) tr []
    | Some (fc,tc), (f,t) :: tr, [] when f <= tc && t <= tc -> calc (Some (fc,tc)) tr []
    | Some (fc,tc), x, [] -> [fc,tc] @ x

它使用 c 参数来存储当前间隔（在其中合并重叠范围），而 l1 和 l2 是两个 int * int列表。

语法很简单，每行表示一个具有 c ， l1 和 l2 以精确方式指定的单个用例。 让我给你一些例子：

(Some (fc,tc) as cur), (f1,t1) :: y1, ((f2,t2) :: y2 as n2) when t1 <= fc -> calc cur y1 n2

我有一个当前范围fc,tc，两个列表至少包含一个元素（这就是为什么有(f1,t1)::y1），所以如果t1 <= fc，那么第一个列表的范围在当前范围之前结束，可以被丢弃，因此它会递归地调用自身，使用相同的cur范围，y1其中第一个被丢弃，n2是作为参数接收的同一列表的别名。

对于每种情况都类似，当我发现没有下一个范围与cur重叠时，我将cur作为最终答案的一个元素返回，并从空白开始重新开始。

- Jack

---

我想知道你是否介意稍微解释一下语法。只需要足够理解这个想法就可以了... :) - Dr. belisarius

Answer 5

我假设每个范围本身都是不重叠的、最小的，并且是有序的。

如果是这样的话，你可以把它们“压缩”起来：

1. 取最早开始的区间
2. 如果另一个范围的下一个区间的开始时间在此区间结束之后，则输出此区间并转到1
3. 如果另一个范围的下一个区间结束时间在此区间之前，则丢弃该区间并转到2
4. 将另一个区间的开始设置为此区间的开始，丢弃此区间，并转到1

之后，您可以遍历并合并相邻的区间（如果需要）。

可能有一些小的优化可用，但这基本上实现了联合操作，并应该展示了实现交集的一般过程。

- Anon.