Untitled

case class Item(label: String, weight: Int)

// | アイテム | 重み |
// | a       | 1 |
// | c       | 3 |
// | b       | 2 |
val items = List(
  Item("a", 1),
  Item("c", 3),
  Item("b", 2)
)

val distribution = items.foldLeft((0, List.empty[(Item,Int)])) { (res,item) =>
  val sum = res._1 + item.weight
  (sum, res._2 :+ (item, sum))
}

// res: (Int, List[(Item, Int)]) = (6,List((Item(a,1),1), (Item(c,3),4), (Item(b,2),6)))

// | アイテム | 重み |
// | a       | 1 |
// | c       | 3 |
// | b       | 2 |
// から
// | アイテム | 累積重み |
// | a       | 1 |
// | c       | 4 |
// | b       | 6 |
// という分布 distribution を作成したことになる。

/** 0以上6未満の乱数を生成する */
def random = {
  val r = math.random
  r * distribution._1
}

// 0以上6未満の乱数が、以下の数直線上のどこにプロットされるかを考える。
//
// 0__1________5__6
//
// 乱数rより大きい累積重みを左から順に探せばよい。
// すると、
// 0 <= r < 1 なら a
// 1 <= r < 4 なら c
// 4 <= r < 6 なら b
// が選択される。
// a,b,cそれぞれに対してrの値域を計算してみると、それぞれ1:3:2となる。
// 乱数が一様分布にそっていれば、a,b,cの出現する割合も1:3:2となるはずである。
def sample: Item = {
  val r = random
  distribution._2.find(_._2 > r).get._1
}

(0 to 600000).foldLeft(Map.empty[String, Int]) { (freq, _) =>
  val s = sample
  freq.updated(s.label, freq.getOrElse(s.label, 0) + 1)
}

// それっぽい分布になる
// res73: scala.collection.immutable.Map[String,Int] = Map(b -> 199610, a -> 100090, c -> 300301)