http://www.perlmonks.org?node_id=158539

in reply to Rolling a biased die

Hi

This one's bugged me before, but I think you can do it with full accuracy by creating a hash where the keys represent the bounds between different probabilities. For speed, I'm checking the most likely results first in the second iteration:

sub weightedprob { my %bias = @_; my (\$total, %boundaries); # prepare the boundary map foreach ( sort { \$bias{\$b} <=> \$bias{\$a} } keys %bias ) { \$total += \$bias{\$_}; \$boundaries{\$total} = \$_; } # get a random place on the boundary map, look it up my \$random = rand(\$total); foreach ( sort { \$a <=> \$b } keys %boundaries ) { return \$boundaries{\$_} if \$random < \$_; } } my \$result = weightedprob( 1 => 3.1, 2 => 2.0234, 3 => 1.7, 4 => 1.542232, 5 => 1.321249563, 6 => 1.0142, );

I'm not sure if there's a neater way of doing it without having to iterate the hash twice; maybe not, as you need to know the aggregate value of all the values of the weighted die first.

Update: yep, there is a way, as IO ably demonstrated above. I didn't quite see how his/her algorithm was intended. It's shorter, and faster (by about three times, by my Benchmark). I'll doze off again.

//=\\