Weighted Selection

WeightedSelection.scala

import java.util.Random

case class WeightedItem[T](item: T, weight: Double)

def weightedSelection[T](items: Seq[WeightedItem[T]], numSelections: Int, r: Random): Seq[T] = {
  val (alternativesBackwards, limit) = items.foldLeft((Seq.empty[(Double, T)], 0.0)){(acc, wi) =>
    val (items, weightSum): (Seq[(Double, T)], Double) = acc
    val newWeightSum: Double = wi.weight + weightSum
    val newItems: Seq[(Double,  T)] = (newWeightSum, wi.item) +: items
    (newItems, newWeightSum)
  }
  val alternatives = alternativesBackwards.reverse
  
  def select(selections: Seq[T], selectionsRemaining: Int): Seq[T] = {
    if (selectionsRemaining == 0) selections.reverse
    else {
      val selectIdx = r.nextDouble() * limit
      val selected = alternatives.dropWhile{_._1 < selectIdx}.head._2
      select(selected +: selections, selectionsRemaining - 1)
    }
  }
  
  select(Seq.empty[T], numSelections)
}