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

` `

## No comments:

Post a Comment