#!/usr/bin/perl 

# $selection = rand_dist_weighted( \%dist, \@key_order, $total_weight )
#   Select an element from %dist.  The total of the weights, and the
#   keys sorted by their weights can be provided, or else they are
#   computed.
sub rand_dist_weighted {
    my( $dist, $key_order, $total_weight ) = @_;
    my $running_weight;

    $key_order = [ sort { $dist->{$a} <=> $dist->{$b} } keys %$dist ]
        unless $key_order;
    unless ( $total_weight ) {
        foreach (@$key_order) { $total_weight += $dist->{$_} }
    }

    # Get a random value.
    my $rand = rand( $total_weight );

    # Use it to determine a key.
    foreach my $key (@$key_order) {
        return $key if ($running_weight += $dist->{$key}) >= $rand;
    }
}

%smartie_weights = ( orange => 3, green => 10, pink => 8, brown => 10,
		    tan => 0, red => 6, blue => 11, yellow => 7,
		    purple => 5);

print rand_dist_weighted( \%smartie_weights ), "\n";

$smartie_weight = 0;
@smartie_order = sort { $smartie_weights{$a} <=> $smartie_weights{$b} }
    keys %smartie_weights;
for (@smartie_order) { $smartie_weight += $smartie_weights{$_} }

for ( 0..50 ) {
    print rand_dist_weighted( \%smartie_weights, \@smartie_order,
        $smartie_weight ), "\n";
}