Picking random element by user defined weights [duplicate]

Question

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).

Answer 1

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];