Picking random element by user defined weights

algorithm, php, random

Solution

I use this function in several PHP game engines:

<?php
/**
 * @param array $values - just the weights
 * @return integer A number between 0 and count($values) - 1
 */
function getBucketFromWeights($values) {
    $total = $currentTotal = $bucket = 0;
    $firstRand = mt_rand(1, 100);

    foreach ($values as $amount) {
        $total += $amount;
    }

    $rand = ($firstRand / 100) * $total;

    foreach ($values as $amount) {
        $currentTotal += $amount;

        if ($rand > $currentTotal) {
            $bucket++;
        }
        else {
            break;
        }
    }

    return $bucket;
}

Usage

Suppose I have the user weights in an associative array where each string points to its weight:

$weighted_strings = array(
    "important string" => 100,
    "terrible string" => 10,
    "never string" => 0,
    // etc
);

If I wanted to pull a string based on weight, I'd do this:

$weights = array_values($weighted_strings);
$strings = array_keys($weighted_strings);
$index = getBucketFromWeights($weights);
$selectedString = $strings[$index];

Problem

Possible Duplicate: Generating random results by weight in PHP? I have a web application where users can add 1-20 strings of text and assign a weight to them of how often it should show up. The system would then choose a random string based on the defined weights. What is the best way to go about this? Do the range values for the weight for each string matter? Could I just have the user assign a number (0-100) for each string? How would you go about choosing a random string? (Each choice doesn't worry about what was chosen before, every string has the same odds (based on weight) of being chosen at the start of each call).

Original source

Related problems