는 기능적으로 모든 중복 범위는 사라질 것을 내가 너무 병합해야 범위-개체의 번호가

Question

목록에서 번호-범위를 중복 병합하는 방법 :

3 40 
    1 45 
    2 50 
70 75 
75 90 
80 85 
100 200 

: 여기

case class Range(from:Int, to:Int) 

val rangelist = List(Range(3, 40), Range(1, 45), Range(2, 50), etc) 

범위입니다

1 50 
70 90 
100 200 

명령 적 알고리즘 :

일단 우리가 얻을 것 완료

1. 첫 번째 range-obj를 Pop()하고 다른 나머지 범위와 비교하여 목록의 나머지 부분을 반복합니다.
2. 겹치는 항목이있는 경우 을 병합하여 (새 Range 인스턴스를 생성 함) 원본 목록에서 2 개의 병합 후보를 삭제합니다.
3. 목록 끝에 Range 개체 (병합을 통해 여러 번 변경되었을 수 있음)를 최종 결과 목록에 추가합니다.
4. 다음 항목과 함께이 작업을 반복하십시오.
5. 소스 목록이 비어 있으면 완료됩니다.

은 명령 적으로 하나가 더 기능적 접근이 있다면 그래서 내가 궁금하네요

등 임시 변수의 많은 색인 루프를 작성해야합니다 이렇게하려면?

pop() PLUS 을 제공하면서 소스 컬렉션이 스택처럼 동작 할 수 있어야합니다. 인덱스를 반복하면서 인덱스별로 항목을 삭제할 수 있지만 더 이상 기능을 수행 할 수는 없습니다.

Answer 1

시도 꼬리 재귀가. (주석은 꼬리 재귀 최적화가 발생하지 않을 경우에만 경고 할 필요가 있으며, 주석 달기 여부와 상관없이 컴파일러가 수행합니다.)

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)) 

Answer 2

나는 퍼즐 이러한 종류의 사랑 :

case class Range(from:Int, to:Int) { 
    assert(from <= to) 

    /** Returns true if given Range is completely contained in this range */ 
    def contains(rhs: Range) = from <= rhs.from && rhs.to <= to 

    /** Returns true if given value is contained in this range */ 
    def contains(v: Int) = from <= v && v <= to 
} 

def collapse(rangelist: List[Range]) = 
    // sorting the list puts overlapping ranges adjacent to one another in the list 
    // foldLeft runs a function on successive elements. it's a great way to process 
    // a list when the results are not a 1:1 mapping. 
    rangelist.sortBy(_.from).foldLeft(List.empty[Range]) { (acc, r) => 
    acc match { 
     case head :: tail if head.contains(r) => 
     // r completely contained; drop it 
     head :: tail 
     case head :: tail if head.contains(r.from) => 
     // partial overlap; expand head to include both head and r 
     Range(head.from, r.to) :: tail 
     case _ => 
     // no overlap; prepend r to list 
     r :: acc 
    } 
    } 

Answer 3

여기 내 솔루션입니다 :

def merge(ranges:List[Range]) = ranges 
    .sortWith{(a, b) => a.from < b.from || (a.from == b.from && a.to < b.to)} 
    .foldLeft(List[Range]()){(buildList, range) => buildList match { 
    case Nil => List(range) 
    case head :: tail => if (head.to >= range.from) { 
     Range(head.from, head.to.max(range.to)) :: tail 
    } else { 
     range :: buildList 
    } 
    }} 
    .reverse 

merge(List(Range(1, 3), Range(4, 5), Range(10, 11), Range(1, 6), Range(2, 8))) 
//List[Range] = List(Range(1,8), Range(10,11))