S25

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

view plainprint?

1. // P25 (*) Generate a random permutation of the elements of a list.  
2. // Hint: Use the solution of problem P23.  
3. // Example:  
4. // scala> randomPermute(List('a, 'b, 'c, 'd, 'e, 'f))  
5. // res0: List[Symbol] = List('b, 'a, 'd, 'c, 'e, 'f)  
6.   
7. // P20 (*) Remove the Kth element from a list.  
8. def removeAt[T](i: Int, xs: List[T]) = {  
9.   def r(i: Int, xs: List[T], acc: List[T]): (List[T], T) = (i, xs) match {  
10.     case (0, h :: t) => (acc.reverse ::: t, h)  
11.     case (i, h :: t) => r(i - 1, t, h :: acc)  
12.   }  
13.   if(i < 0 || xs.size <= i) throw new NoSuchElementException else r(i, xs, Nil)  
14. }  
15.   
16. import scala.util.Random  
17. def randomPermute[T](xs: List[T]) = {  
18.   val rand = new Random  
19.   def r(ys: List[T], acc: List[T]): List[T] = {  
20.     if(ys.size == 1) ys.head :: acc  
21.     else {  
22.       val (rest, removed) = removeAt(rand.nextInt(ys.size), ys)  
23.       r(rest, removed :: acc)  
24.     }  
25.   }  
26.   if(xs.isEmpty) Nil else r(xs, Nil)  
27. }  

// P25 (*) Generate a random permutation of the elements of a list.
// Hint: Use the solution of problem P23.
// Example:
// scala> randomPermute(List('a, 'b, 'c, 'd, 'e, 'f))
// res0: List[Symbol] = List('b, 'a, 'd, 'c, 'e, 'f)

// P20 (*) Remove the Kth element from a list.
def removeAt[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)
}

import scala.util.Random
def randomPermute[T](xs: List[T]) = {
  val rand = new Random
  def r(ys: List[T], acc: List[T]): List[T] = {
    if(ys.size == 1) ys.head :: acc
    else {
      val (rest, removed) = removeAt(rand.nextInt(ys.size), ys)
      r(rest, removed :: acc)
    }
  }
  if(xs.isEmpty) Nil else r(xs, Nil)
}

解答例
またもや、してやられたぜ！