random toss of discrete values with (integer) probability distribution

[spir <denis.spir@...>]

Hello,

This is more an algorithmic question than a Lua-related one, however I thought 
others may be interested, since it touches a recurring issue in 
game-programming, i guess.

The problem is, how to toss a choice in a set of discrete values, each having a 
relative probability (represented by an integer, sometimes a %age). To make 
things more concrete, say there are 3 choices a,b,c, which probability law 
(distribution) looks like this:

	  X
	X X
	X X X
	-----
	a b c

What we want is toss according to these relative probabilities.

A simple solution is to make a "sampling set"
	{a,a, b,b,b, c}
and randomly toss in there.

However, this may be very costly due to the construction of the set-table. It's 
only good when tossing multiple times from the same set, which is not the 
general case. In my case, values are terrain codes for a map generator. I want 
each tile to be tossed according to user-given probabilities for each terrain, 
but above all taking into account types of already defined surrounding tiles, 
and weighted by a homogeneity factor (which multiplies cardinality of each 
terrain code of defined neighbour tiles). This means a sampling set should be 
constructed for each tile, and it can be big (0 <= homogeneity <= 100, meaning 
max size is 600 for a hex map).
I could have a table of max size, and just override its items, then toss among 
actual number of codes. But this still seems a bit stupidly costly.

Another solution I thought at is to use a multiset, with cardinalities 
represents relative probabilities of codes:
	{{a,2}, {b,3}, {c,1}}
Actually, if codes are plain ordinals, then it can just be:
	{2, 3, 1}	-- sum = 6
I'd just toss random(6), then iterate on cardinalities (summing on the way) 
until I reach a value >= toss result.

This is the best I could find for now. But I still have the impression of 
missing an obvious point...
What do you think?

Thank you,
Denis