## 5/21/09

### 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)
}
}``````
` `