File Coverage

blib/lib/Math/Random/Discrete.pm

Criterion	Covered	Total	%
statement	39	39	100.0
branch	7	8	87.5
condition	2	3	66.6
subroutine	4	4	100.0
pod	2	2	100.0
total	54	56	96.4

package Math::Random::Discrete;
{
  $Math::Random::Discrete::VERSION = '1.01';
}
use strict;
use warnings;

# ABSTRACT: Discrete random variables with general distributions

# This is an implementation of Walker's alias method.

sub new {
    my ($class, $_weights, $values) = @_;

    my @weights = @$_weights;

    # compute average weight

    my $N   = @weights;
    my $sum = 0;

    for my $weight (@weights) {
        $sum += $weight;
    }

    my $avg = $sum / $N;

    # split weights into two groups: smaller and larger than average

    my (@small, @large);

    for (my $i = 0; $i < $N; ++$i) {
        if ($weights[$i] <= $avg) {
            push(@small, $i);
        }
        else {
            push(@large, $i);
        }
    }

    # generate F and A arrays

    my (@F, @A);

    while (@small and @large) {
        my $i  = pop(@small);
        my $j  = $large[-1];
        $A[$i] = $j;
        $F[$i] = $weights[$i] / $avg;

        $weights[$j] -= $avg - $weights[$i];

        push(@small, pop(@large))
            if $weights[$j] <= $avg;
    }

    for my $i (@small, @large) {
        $A[$i] = $i;
        $F[$i] = 1.0;
    }

    # create blessed ref

    my $self = {
        values => $values,
        A      => \@A,
        F      => \@F,
    };

    return bless($self, $class);
}

sub rand {
    my $self = shift;

    my $F  = $self->{F};
    my $r  = CORE::rand(@$F);
    my $ri = int($r);  # integer part
    my $rf = $r - $ri; # fractional part

    my $i = $rf < $F->[$ri] ? $ri : $self->{A}[$ri];

    my $values = $self->{values};

    return $values ? $values->[$i] : $i;
}

1;

__END__