병합 반전 수가 사용 포함 해서요 정렬 I 정렬 병합하여 반전의 수를 카운트 할 필요

Question

:

object Example { 
def msort(xs: List[Int]): List[Int] = { 
    def merge(left: List[Int], right: List[Int]): Stream[Int] = (left, right) match { 
     case (x :: xs, y :: ys) if x < y => Stream.cons(x, merge(xs, right)) 
     case (x :: xs, y :: ys) => Stream.cons(y, merge(left, ys)) 
     case _ => if (left.isEmpty) right.toStream else left.toStream 
    } 

    val n = xs.length/2 
    if (n == 0) xs 
    else { 
     val (ys, zs) = xs splitAt n 
     merge(msort(ys), msort(zs)).toList 
    } 
    }            

    msort(List(8, 15, 3))       
} 

을 난 라인에서 계산해야 추측 (여기서 y < y, match에서 두 번째 행)

case (x :: xs, y :: ys) => Stream.cons(y, merge(left, ys)) 

그러나 시도한 결과 실패했습니다.

어떻게하면됩니까?

UPDATE : 어큐뮬레이터와

버전 :

def msort(xs: List[Int]): List[Int] = { 
    def merge(left: List[Int], right: List[Int], inversionAcc: Int = 0): Stream[Int] = (left, right) match { 
     case (x :: xs, y :: ys) if x < y => Stream.cons(x, merge(xs, right, inversionAcc)) 
     case (x :: xs, y :: ys) => Stream.cons(y, merge(left, ys, inversionAcc + 1)) 
     case _ => if (left.isEmpty) right.toStream else left.toStream 
    } 

    val n = xs.length/2 
    if (n == 0) xs 
    else { 
     val (ys, zs) = xs splitAt n 
     merge(msort(ys), msort(zs)).toList 
    } 
    } 

어떻게 쉽게 inversionAcc을 반환합니까? 이 튜플의 일부만 돌려 줄 수 있습니다.

def merge(left: List[Int], right: List[Int], invariantAcc: Int = 0): (Stream[Int], Int) 

그래도 좋지 않습니다.

UPDATE2는 : 오류가 어디

하고 실제로 제대로을 계산하지 않습니다, 나는 찾을 수 없습니다.

Answer 1

이것은 Frege solution의 스칼라 포트입니다.

object CountInversions { 

    def inversionCount(xs: List[Int], size: Int): (Int, List[Int]) = 
    xs match { 
     case _::_::_ => { //If the list has more than one element 
      val mid = size/2 
      val lsize = mid 
      val rsize = size - mid 
      val (left, right) = xs.splitAt(mid) 
      val (lcount, lsorted) = inversionCount(left, lsize) 
      val (rcount, rsorted) = inversionCount(right, rsize) 
      val (mergecount, sorted) = inversionMergeCount(lsorted, lsize, rsorted, 
      rsize, 0, Nil) 
      val count = lcount + rcount + mergecount 
      (count, sorted) 
     } 
     case xs => (0, xs) 
    } 

    def inversionMergeCount(xs: List[Int], m: Int, ys: List[Int], n: Int, 
    acc: Int, sorted: List[Int]): (Int, List[Int]) = 
     (xs, ys) match { 
     case (xs, Nil) => (acc, sorted.reverse ++ xs) 
     case (Nil, ys) => (acc, sorted.reverse ++ ys) 
     case (x :: restx, y :: resty) => 
      if (x < y) inversionMergeCount(restx, m - 1, ys, n, acc, x :: sorted) 
      else if (x > y) inversionMergeCount(xs, m, resty, n - 1, acc + m, y :: sorted) 
      else inversionMergeCount(restx, m - 1, resty, n - 1, acc, x :: y :: sorted) 
     } 

} 

Answer 2

솔루션이 엄격하게 기능해야하지 않는 경우 당신은 그냥 단순한 카운터 추가 할 수 있습니다 :이 기능을 유지하는 경우

object Example { 
    var inversions = 0 
    def msort(xs: List[Int]): List[Int] = { 
    def merge(left: List[Int], right: List[Int]): Stream[Int] = (left, right) match { 
     case (x :: xs, y :: ys) if x < y => Stream.cons(x, merge(xs, right)) 
     case (x :: xs, y :: ys) => 
     inversions = inversions + 1 
     Stream.cons(y, merge(left, ys)) 
     case _ => if (left.isEmpty) right.toStream else left.toStream 
    } 

    val n = xs.length/2 
    if (n == 0) xs 
    else { 
     val (ys, zs) = xs splitAt n 
     merge(msort(ys), msort(zs)).toList 
    } 
    } 
} 
Example.msort(List(8, 15, 3)) 
println(Example.inversions) 

은 다음 어큐뮬레이터를 작성하고 그것을 통해 스레드해야합니다을 모든 메소드를 호출하고 누적 값이 반환 결과에 포함 된 각 함수에서 쌍을 반환 한 다음 각 병합 수렴에 대한 누적 값을 합계합니다. (내 기능 - fu는별로 좋지 않습니다. 간단한 접근 방식을 시도하기 전에 이미이 기능적으로 해결하려고했습니다.)