My take on 99 problems in Scala (23 to 26)

I have lot of things going on, but a quick post. Here are 5 more problems solved in Scala.
Note: in all this and the previous solutions, I've left out (most of the time) boundary conditions checks, to keep the code simple and as elegant as possible.

P23: Random select. We reuse P20 (removeAt) and remove a random element of the list recursively.


//P23

  def randomSelect[A](n: Int, xs: List[A]): List[A] = (n, xs) match {
    case (_, Nil) => Nil
    case (0, _) => Nil
    case (_, _) => {
      val x = removeAt(new Random().nextInt(xs.size), xs)
      x._2 :: randomSelect(n - 1, x._1)
    }
  }

P24: lotto. we create a list (well, actually is a range converted to a list) of the numbers and use P23 to select a random draw.


//P24
def lotto(n:Int,max:Int):List[Int] =randomSelect(n,(1 to max).toList)


P25: random permute. That's easy: we use P23 to do a randomSelect on the whole list


//P25
def randomPermute[A](xs:List[A]):List[A] =randomSelect(xs.size,xs)


P26: combinations. That one wasn't straightforward, I actually had to think! :)
But the solution can be defined recursively:
to get the combinations of size n, take one element of the set and append it to all the combinations of sets of size n-1 of the remaining elements, union the combinations of size n of the remaining elements.
I had to create an auxiliary function that "lift" a list into a list of lists, (kind of the opposite of flatten).


//P26

  def combinations[A](n: Int, xs: List[A]): List[List[A]] = {
    def lift[A](xs: List[A]): List[List[A]] = xs.foldLeft(List[List[A]]())((ys, y) => (List(y) :: ys))

    (n, xs) match {
      case (1, ys) => lift(ys)
      case (i, xs) if (i == xs.size) => xs :: Nil
      case (i, ys) => combinations(i - 1, ys.tail).map(zs => ys.head :: zs) ::: combinations(i, ys.tail)
    }
  }