gistfile1.scala

  def weightedShuffle[T](ts: List[T], weight: T => Int): List[T] = {
    case class ValueAndCumulativeWeight(t: T, cumWeight: Int)
    @tailrec def weightedShuffle0(ts: List[T], weight: T => Int, acc: List[T]): List[T] = ts match {
      case Nil         => acc
      case only :: Nil => acc :+ only
      case head :: tail => {
        val selection = Randoms.randomInt(0, ts.map(weight).sum)
        val choice = tail
          .scanLeft(ValueAndCumulativeWeight(head, weight(head)))((soFar, x) => ValueAndCumulativeWeight(x, soFar.cumWeight + weight(x)))
          .find(_.cumWeight >= selection)
          .get.t
        weightedShuffle0(ts diff Seq(choice), weight, acc :+ choice)
      }
    }

    weightedShuffle0(ts, weight, List.empty)
  }