S-99 P21-P25

p21-p25.scala

// P21
def insertAt[A](e: A, i: Int, ls: Seq[A]): Seq[A] = ls.take(i) ++ Seq(e) ++ ls.drop(i)

// P22
def range(start: Int, end: Int): Seq[Int] = Seq.range(start, end+1)

def rangeR(start: Int, end: Int): Seq[Int] = {
  def rangeRR(value: Int, result: Seq[Int]): Seq[Int] = {
    if(value < start) result
    else rangeRR(value-1, value +: result)
  }
  rangeRR(end, Nil)
}

// P23
def randomSelect[A](n: Int, ls: Seq[A]): Seq[A] = {
  def randomSelectR[A](n: Int, ls: Seq[A], r: util.Random): Seq[A] = {
    if (n <= 0 || ls.isEmpty) Seq.empty
    else{
      val index = r.nextInt(ls.length)
      ls(index) +: randomSelect(n-1, removeAt(index, ls)._1)
    }
  }
  randomSelectR(n, ls, new util.Random)
}

// P24
def lotto(n: Int, max: Int): Seq[Int] = {
  def lottoR(n: Int, max: Int, r: util.Random): Seq[Int] = {
    if (n <= 0) Seq.empty
    else{
      r.nextInt(max) +: lottoR(n-1, max, r)
    }
  }
  lottoR(n, max, new util.Random)
}

// P25
def randomPermute[A](ls: Seq[A]): Seq[A] = {
  def randomPermuteR[A](ls: Seq[A], r: util.Random): Seq[A] = {
    if(ls.isEmpty) Seq.empty
    else{
      val (l, value) = removeAt(r.nextInt(ls.length), ls)
      value +: randomPermuteR(l, r)
    }
  }
  randomPermuteR(ls, new util.Random)
}