S-99 P26-P28(P30)

p26-p28.scala

// P26
// 大門.scala gist(https://gist.github.com/1183495)よりほぼ転載
def sublists[A](ls: List[A]): List[List[A]] = ls match{
  case Nil => Nil
  case _ :: tail => ls :: sublists(tail)
}

def combinations[A](n: Int, ls: List[A]): List[List[A]] = {
  if (n == 0) List(Nil)
  else{
    def execute(lis: List[A]): List[List[A]] = {
      combinations(n-1, ls.tail) map {ls.head :: _}
    }
    sublists(ls) flatMap {execute}
  }
}

def rep[A](n: Int, list: List[A]): List[List[A]] = {
  if (n == 0) List(Nil)
  else{
    def execute(ls: List[A]): List[List[A]] = {
      rep(n-1, ls) map {ls.head :: _}
    }
    sublists(list) flatMap {execute}
  }
}

// P27(a)
def group3[A](ls: List[A]): List[List[List[A]]] = {
  for{a <- combinations(2, ls)
      lst = ls filterNot {a.contains}
      b <- combinations(3, lst)
    } yield List(a, b, lst filterNot {b.contains})
}

// P27(b)
def group[A](ns: List[Int], ls: List[A]): List[List[List[A]]] = ns match{
  case Nil => List(Nil)
  case n :: ns => combinations(n, ls) flatMap { e =>
    group(ns, ls filterNot {e.contains}) map {e :: _}}
}


// P28(a)
def lsort[A](ls: List[List[A]]): List[List[A]] = ls.sortBy(_.length)

// P28(b)
def lsortFreq[A](ls: List[List[A]]): List[List[A]] = {
  def countFreq[A](ls: List[List[A]]): Map[Int, Int] = {
    if (ls.isEmpty) Map.empty
    else{
      val (n, ns) = ls.span(ls.head.length == _.length)
      val freq = n.length
      countFreq(ns) + (ls.head.length -> freq)
    }
  }
  val freqMap = countFreq(ls.sortBy(_.length))
  ls.sortWith((a, b) => freqMap(a.length) < freqMap(b.length))
}