如何从List中功能合并重叠的数字范围 [英] How to functionally merge overlapping number-ranges from a List

问题描述

我有一些需要合并的范围对象，以便所有重叠范围消失：

  case class Range （范围（3,40），范围（1，45），范围（2,50）等）
  

以下是范围：

  3 40 
 1 45 
 2 50 
 70 75 
 75 90 
 80 85 
 100 200 
  
 
  
 
完成后， 1 50 
 70 90 
 100 200 
  
命令式算法：
 
 
 Pop（）第一个range-obj并遍历列表的其余部分，并将其与其他每个范围进行比较。如果有重叠的项目，
将它们合并在一起（这会产生一个新的Range实例），并从源列表中删除2个合并候选项。 
 
 
在列表的末尾添加Range对象（它可以通过合并多次更改）到最终结果列表。
 
 
对剩下的其他项目重复此操作。 
 
 
一旦源列表为空，我们就完成了。
 
 
要做到这一点，势在必行你必须创建很多临时变量，索引循环等。
 
 
 
所以我想知道是否有更多的功能方法？
 
 
初看起来，source-collection必须能够像Stack一样提供pop（）PLUS 
，以便能够在遍历迭代时按索引删除项目，但那样做不会这个功能已经解决了。
解决方案
试试tail-recursion。 （如果没有发生尾递归优化，只需要注释来警告您;编译器会在没有注释的情况下执行它。）
 导入注释。{tailrec => tco} 
 @tco final def collapse（rs：List [Range]，sep：List [Range] = Nil）：List [Range] = rs match {
 case x :: y :: rest = > 
 if（y.from> x.to）collapse（y :: rest，x :: sep）
 else collapse（Range（x.from，x.to max y.to）::休息，sep）
案例_ => 
（rs ::: sep）.reverse 
} 
 def merge（rs：List [Range]）：List [Range] = collapse（rs.sortBy（_。from））
  
 
I have a number of range-objects which I need to merge so that all overlapping ranges disappear:
case class Range(from:Int, to:Int)

val rangelist = List(Range(3, 40), Range(1, 45), Range(2, 50), etc)
Here is the ranges:
  3  40  
  1  45  
  2  50  
 70  75  
 75  90  
 80  85  
100 200
Once finished we would get:
  1  50  
 70  90  
100 200  
Imperative Algorithm:

Pop() the first range-obj and iterate through the rest of the list comparing it with each of the other ranges.  
if there is an overlapping item,
merge them together ( This yields a new Range instance ) and delete the 2 merge-candidates from the source-list.  
At the end of the list add the Range object (which could have changed numerous times through merging) to the final-result-list.
Repeat this with the next of the remaining items.  
Once the source-list is empty we're done.
To do this imperatively one must create a lot of temporary variables, indexed loops etc.

So I'm wondering if there is a more functional approach?

At first sight the source-collection must be able to act like a Stack in providing pop() PLUS
giving the ability to delete items by index while iterating over it, but then that would not be that functional anymore.
解决方案
Try tail-recursion.  (Annotation is needed only to warn you if tail-recursion optimization doesn't happen; the compiler will do it if it can whether you annotate or not.)
import annotation.{tailrec => tco}
@tco final def collapse(rs: List[Range], sep: List[Range] = Nil): List[Range] = rs match {
  case x :: y :: rest =>
    if (y.from > x.to) collapse(y :: rest, x :: sep)
    else collapse( Range(x.from, x.to max y.to) :: rest, sep)
  case _ =>
    (rs ::: sep).reverse
}
def merge(rs: List[Range]): List[Range] = collapse(rs.sortBy(_.from))


                        
这篇关于如何从List中功能合并重叠的数字范围的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！