Picking random element by user defined weights

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

Related: http://stackoverflow.com/questions/4463561/weighed-random-selection-from-array/4463613#4463613 — Sven Marnach, Jan 18 '11 at 16:16
This question comes up often. Here's a good one with a simple answer: http://stackoverflow.com/questions/445235/generating-random-results-by-weight-in-php — Mark Ransom, Jan 18 '11 at 16:17

score 6 · Accepted Answer · answered Jan 18 '11 at 16:15

6

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

answered Jan 18 '11 at 16:15

Kyle Wild

8,845
2
36
36

2

This can be further optimised if you build a reverse associative array where the keys are the totals of the weights so far and the values are the strings, so something like this: `0 => "important string", 100 => "terrible string", 110=> "never string"`, this enables you to find the selected element using binary search. Of course for only a handful of elements it's not worth the effort. – biziclop Jan 18 '11 at 16:26
@biziclop If you're going to do a binary search, there's really no benefit in using an associative array instead of a sorted list. – Nick Johnson Jan 18 '11 at 22:33
The code it works, but I cannot understand the logic. Can you explain me how exactly it works. I mean for example what is the goal of this line: $rand = ($firstRand / 100) * $total; – Anton_Sh Sep 11 '15 at 10:17
@Anton_Sh: The idea is to convert weights to percentages. Firstly, he generates a random number from 1-100 (percentage), then converts it to weights with that line. Secondly, with the `for` loop, he finds which part (think of bars with different lengths) the random number fall in, and returns the index of that part. However, I think `$rand = ($firstRand / 100) * $total;` is still redundant. Why didn't he use `mt_rand(0, $total)` in the first place? – alumi Apr 13 '17 at 10:14

score 1 · Answer 2 · answered Jan 18 '11 at 17:26

Here is a simple implementation:

function Probability($data, $number = 1)
{
    $result = array();

    if (is_array($data) === true)
    {
        $data = array_map('abs', $data);
        $number = min(max(1, abs($number)), count($data));

        while ($number-- > 0)
        {
            $chance = 0;
            $probability = mt_rand(1, array_sum($data));

            foreach ($data as $key => $value)
            {
                $chance += $value;

                if ($chance >= $probability)
                {
                    $result[] = $key; unset($data[$key]); break;
                }
            }
        }
    }

    return $result;
}

With this function you can specify how many unique weighted random elements you want (IDEOne).

Picking random element by user defined weights

2 Answers2

Linked