重み付きランダム

重み付きランダムについて。
たとえば、サイコロを用意する。Aと書いてある面が3つ、Bと書いてある面が2つ、Cと書いてある面が1つあるとする。
これを振ると、AとBとCの出る確率を比率で表すと、3:2:1になる。
こういう結果に偏りのあるサイコロをプログラムで書くと非常に面倒である。
そこで、簡単になるアルゴリズムを使う。

アルゴリズム

先のサイコロの例であげると、こういうマトリクスを用意する。

	1	2	3
1	A	A	A
2	B	B	r
3	C	r	r

このマトリクスで、横軸と縦軸につき乱数を発生させる。
横軸は、１から比率の最大値までの乱数であり、縦軸は、結果の項目数の乱数である。
この二つの乱数の交点がrであれば、最初に戻って振りなおしである。
そうでなければ、そこに書いてある文字を結果として採用、返せばよいことになる。

luaによる例

function weighted_choice(weighted) -- 重み付きランダム。
	-- weighted は配列型のテーブルとする。
	-- 各項目には数値が入っており、これをランダムに使用する重みとする。
	-- 例）{1=3, 2=5, 3=8}
	-- 1〜項目数の範囲で乱数を返すが、何が返ってくるかは先のテーブルで定義された重みに従う。
	-- 例の場合は1から3の数値のどれかが返ってくるが、3が一番出やすく、1が最も出にくい。
	-- もし、重みの最低値が1未満であったならば、その数値が1になるように全ての重みに加算を行う。
	
	if type(weighted) ~= "table" then return nil end -- テーブルしか受け付けませんよ。
	local max = nil -- 重みの最大値
	local min = nil -- 重みの最小値
	local count = #weighted -- 項目数
	for i, v in ipairs(weighted) do -- 重みの最小値と最大値を求める。
		max = max or i
		if max < i then max = i end
		min = min or i
		if min > i then min = i end
	end
	if min > 1 then min = 1 end

	min = min - 1
	max = max - 1

	local res
	local dice
	while true do
		res = math.random(count)
		dice = math.random(min, max)
		if weighted[res] > dice then break end
	end
	return res
end