weightedIndex

Randomly selects an index into proportions, where the likelihood of each index is weighted by that proportion. It is more likely for the index of the last proportion to be returned than the index of the first proportion in the slice, and vice versa.

This is useful for selecting an item from a slice where weights are not equal. T must be a numeric type capable of holding the sum of proportions.

Function parameters

Parameters

r:Random
T:type
proportions:[]const T

Fast unbiased random numbers.

Types

DefaultPrng: Fast unbiased random numbers.
DefaultCsprng: Cryptographically secure random numbers.
Ascon
ChaCha
Isaac64
Pcg
Xoroshiro128
Xoshiro256
Sfc64
RomuTrio
SplitMix64
ziggurat

Functions in this namespace

Functions

init
bytes: Read random bytes into the specified buffer until full.
boolean
enumValue: Returns a random value from an enum, evenly distributed.
enumValueWithIndex: Returns a random value from an enum, evenly distributed.
int: Returns a random int `i` such that `minInt(T) <= i <= maxInt(T)`.
uintLessThanBiased: Constant-time implementation off `uintLessThan`.
uintLessThan: Returns an evenly distributed random unsigned integer `0 <= i < less_than`.
uintAtMostBiased: Constant-time implementation off `uintAtMost`.
uintAtMost: Returns an evenly distributed random unsigned integer `0 <= i <= at_most`.
intRangeLessThanBiased: Constant-time implementation off `intRangeLessThan`.
intRangeLessThan: Returns an evenly distributed random integer `at_least <= i < less_than`.
intRangeAtMostBiased: Constant-time implementation off `intRangeAtMostBiased`.
intRangeAtMost: Returns an evenly distributed random integer `at_least <= i <= at_most`.
float: Return a floating point value evenly distributed in the range [0, 1).
floatNorm: Return a floating point value normally distributed with mean = 0, stddev = 1.
floatExp: Return an exponentially distributed float with a rate parameter of 1.
shuffle: Shuffle a slice into a random order.
shuffleWithIndex: Shuffle a slice into a random order, using an index of a
weightedIndex: Randomly selects an index into `proportions`, where the likelihood of each
limitRangeBiased: Convert a random integer 0 <= random_int <= maxValue(T),

Source

Implementation

pub fn weightedIndex(r: Random, comptime T: type, proportions: []const T) usize {
    // This implementation works by summing the proportions and picking a
    // random point in [0, sum).  We then loop over the proportions,
    // accumulating until our accumulator is greater than the random point.

    const sum = s: {
        var sum: T = 0;
        for (proportions) |v| sum += v;
        break :s sum;
    };

    const point = switch (@typeInfo(T)) {
        .int => |int_info| switch (int_info.signedness) {
            .signed => r.intRangeLessThan(T, 0, sum),
            .unsigned => r.uintLessThan(T, sum),
        },
        // take care that imprecision doesn't lead to a value slightly greater than sum
        .float => @min(r.float(T) * sum, sum - std.math.floatEps(T)),
        else => @compileError("weightedIndex does not support proportions of type " ++
            @typeName(T)),
    };

    assert(point < sum);

    var accumulator: T = 0;
    for (proportions, 0..) |p, index| {
        accumulator += p;
        if (point < accumulator) return index;
    } else unreachable;
}