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

4 comments:

Techsaga Corporations said...

A Software development company in Noida has to perform in accord with the client's engineering team for ideal results. Techsaga addresses this facet of the software development process most aggressively with our streamlined and well-planned resources.

Racesite Pro said...

Yes i am totally agreed with this article and i just want to say that this article is very nice and vey informative. More blogs please. 경마사이트

Oncasinosite Net said...

This blog is what im exactly looking for. Great! and Thanks to you. 바카라사이트

Totopick Pro said...

What an interesting article! I'm glad i finally found what i was looking for. 사설토토