S-99: Ninety-Nine Scala Problems(P21-P28)を解いてみた

S-99: Ninety-Nine Scala Problems(P11-P20)を解いてみたの続き。P21-P30ではなく、P21-P28になっているのは、P27とP28がそれぞれ二問ずつあり、P28で一端問題が区切られているため。今回のは、時間を測り忘れていたが、前回よりもややてこずった気がする。以下、回答のコード。

object P21toP28 {
  import P01toP10._
  import P11toP20._
  def mergeSort[T](list: List[T])(lt: (T, T) => Boolean): List[T] = {
    def merge(list1: List[T], list2: List[T]): List[T] = {
      (list1, list2) match {
        case (x::xs, y::ys) if lt(x, y) => x::merge(xs, list2)
        case (x::xs, y::ys) => y::merge(list1, ys)
        case (Nil, ys) => ys
        case (xs, Nil) => xs
      }
    }
    def mergeSort1(list: List[T], len: Int): List[T] = len match {
      case 0 => Nil
      case 1 => list
      case _ => 
        val m = len / 2
        val (fst, snd) = split(m, list)
        merge(mergeSort1(fst, m), mergeSort1(snd, len - m))
    }
    mergeSort1(list, length(list))
  }
  
  def insertAt[T](e: T, index: Int, list: List[T]): List[T] = list match {
    case x if index == 0 => e::x
    case x::xs if index > 0 => x::insertAt(e, index - 1, xs)
    case _ => error("")
  }
  def range(from: Int, to: Int): List[Int] = {
    if(from == to) List(to)
    else if(from < to) from::range(from + 1, to)
    else error("")
  }
  def randomSelect[T](n: Int, list: List[T]): List[T] = {
    def randomSelect1(n: Int, len: Int, list: List[T]): List[T] = {
      if(n == 0) List[T]()
      else if(n > 0) {
        val (rest, e) = removeAt((Math.random * len).toInt, list)
        e::randomSelect1(n - 1, len - 1, rest)
      } else error("")
    }
    val len = length(list)
    if(n <= len) randomSelect1(n, len, list) else error("")
  }
  def lotto(n: Int, m: Int): List[Int] = randomSelect(n, range(1, m))
  def randomPermute[T](list: List[T]): List[T] = randomSelect(length(list), list)
  def groupInto[T](n: Int, k: Int, list: List[T]): List[(List[T], List[T])] = list match {
    case _ if k == n => List((list, Nil))
    case _ if k == 0 => List((Nil, list))
    case x::xs if k > 0 => 
      append(
        map(groupInto(n - 1, k - 1, xs)){a => (x::a._1, a._2)}, 
        map(groupInto(n - 1, k, xs)){a => (a._1, x::a._2)})
    case _ => error("")
  }
  def combinations[T](k: Int, list: List[T]): List[List[T]] = {
    map(groupInto(length(list), k, list))(_._1)
  }
  def group3[T](list: List[T]): List[List[List[T]]] = {
    flatMap(groupInto(9, 2, list)){ case (s1, r) =>
      flatMap(groupInto(7, 3, r)){ case (s2, r) =>
        map(groupInto(4, 4, r)){ case (s3, r) => List(s1, s2, s3) }}}
  }
  def group[T](setting: List[Int], list: List[T]): List[List[List[T]]] = {
    def group_(setting: List[Int], n: Int, list: List[T]): List[List[List[T]]] = {
      setting match {
        case Nil => List(Nil)
        case x::xs => 
          flatMap(groupInto(n, x, list)){ case (s, r) => map(group_(xs, n - x, r))(k => k.::(s)) }
      }
    }
    group_(setting, length(list), list)
  }

  def lsort[T](list: List[List[T]]): List[List[T]] = {
    map(mergeSort(map(list)(x => (x, length(x))))(_._2 < _._2))(_._1)
  }

  def lsortFreq[T](list: List[List[T]]): List[List[T]] = {
    val listl = map(list)(x => (x, length(x)))
    val freqs = foldLeft(listl, Map[Int, Int]()){ case (map, (lst, len)) =>
      map(len) = map.getOrElse(len, 0) + 1
    }
    map(mergeSort(map(listl)(x => (x._1, freqs(x._2))))(_._2 < _._2))(_._1)
  }
}

実行例。

scala> import P21toP28._
import P21toP28._

scala> insertAt('new, 1, List('a, 'b, 'c, 'd))
res0: List[Symbol] = List('a, 'new, 'b, 'c, 'd)

scala> range(4, 9)
res1: List[Int] = List(4, 5, 6, 7, 8, 9)

scala> randomSelect(3, List('a, 'b, 'c, 'd, 'f, 'g, 'h))
res2: List[Symbol] = List('d, 'b, 'c)

scala> lotto(6, 49)
res3: List[Int] = List(43, 7, 36, 25, 32, 34)

scala> randomPermute(List('a, 'b, 'c, 'd, 'e, 'f))
res4: List[Symbol] = List('b, 'f, 'e, 'c, 'd, 'a)

scala> combinations(3, List('a, 'b, 'c, 'd, 'e, 'f))
res5: List[List[Symbol]] = List(List('a, 'b, 'c), List('a, 'b, 'd), List('a, 'b,
 'e), List('a, 'b, 'f), List('a, 'c, 'd), List('a, 'c, 'e), List('a, 'c, 'f), Li
st('a, 'd, 'e), List('a, 'd, 'f), List('a, 'e, 'f), List('b, 'c, 'd), List('b, '
c, 'e), List('b, 'c, 'f), List('b, 'd, 'e), List('b, 'd, 'f), List('b, 'e, 'f),
List('c, 'd, 'e), List('c, 'd, 'f), List('c, 'e, 'f), List('d, 'e, ...
scala> group3(List("Aldo", "Beat", "Carla", "David", "Evi", "Flip", "Gary", "Hug
o", "Ida"))
res6: List[List[List[java.lang.String]]] = List(List(List(Aldo, Beat), List(Carl
a, David, Evi), List(Flip, Gary, Hugo, Ida)), List(List(Aldo, Beat), List(Carla,
 David, Flip), List(Evi, Gary, Hugo, Ida)), List(List(Aldo, Beat), List(Carla, D
avid, Gary), List(Evi, Flip, Hugo, Ida)), List(List(Aldo, Beat), List(Carla, Dav
id, Hugo), List(Evi, Flip, Gary, Ida)), List(List(Aldo, Beat), List...
scala> group(List(2, 2, 5), List("Aldo", "Beat", "Carla", "David", "Evi", "Flip"
, "Gary", "Hugo", "Ida"))
res7: List[List[List[java.lang.String]]] = List(List(List(Aldo, Beat), List(Carl
a, David), List(Evi, Flip, Gary, Hugo, Ida)), List(List(Aldo, Beat), List(Carla,
 Evi), List(David, Flip, Gary, Hugo, Ida)), List(List(Aldo, Beat), List(Carla, F
lip), List(David, Evi, Gary, Hugo, Ida)), List(List(Aldo, Beat), List(Carla, Gar
y), List(David, Evi, Flip, Hugo, Ida)), List(List(Aldo, Beat), List...
scala> lsort(List(List('a, 'b, 'c), List('d, 'e), List('f, 'g, 'h), List('d, 'e)
, List('i, 'j, 'k, 'l), List('m, 'n), List('o)))
res8: List[List[Symbol]] = List(List('o), List('m, 'n), List('d, 'e), List('d, '
e), List('f, 'g, 'h), List('a, 'b, 'c), List('i, 'j, 'k, 'l))

scala> lsortFreq(List(List('a, 'b, 'c), List('d, 'e), List('f, 'g, 'h), List('d,
 'e), List('i, 'j, 'k, 'l), List('m, 'n), List('o)))
res9: List[List[Symbol]] = List(List('o), List('i, 'j, 'k, 'l), List('f, 'g, 'h)
, List('a, 'b, 'c), List('m, 'n), List('d, 'e), List('d, 'e))