Re: Rolling a biased die

[ViceRaid]

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.

//=\\