S23

S-99: Ninety-Nine Scala Problemsを試してみる。
勉強のためにListのAPIはなるべく使わない方向。

// P23 (**) Extract a given number of randomly selected elements from a list.
// Example:
// scala> randomSelect(3, List('a, 'b, 'c, 'd, 'f, 'g, 'h))
// res0: List[Symbol] = List('e, 'd, 'a)

import scala.util.Random

// P20 (*) Remove the Kth element from a list.
def removeAtR[T](i: Int, xs: List[T]) = {
  def r(i: Int, xs: List[T], acc: List[T]): (List[T], T) = (i, xs) match {
    case (0, h :: t) => (acc.reverse ::: t, h)
    case (i, h :: t) => r(i - 1, t, h :: acc)
  }
  if(i < 0 || xs.size <= i) throw new NoSuchElementException else r(i, xs, Nil)
}

def randomSelect[T](n: Int, xs: List[T]) = {
  val rand = new Random()
  def r(ys: List[T], acc: List[T]): List[T] = {
    val (rest, removed) = removeAtR(rand.nextInt(ys.size), ys)
    if(n <= acc.size + 1) removed :: acc
    else r(rest, removed :: acc)
  }
  if(n <= 0 || xs.size < n) throw new IllegalArgumentException
  else r(xs, Nil)
}

解答例
君のは違うけど、わしのは末尾再帰だよ。