3

Assume I want to choose a number from 1-10 at random, but there are weights to each number. 

1 - 15% chance 2 - 15% chance 3 - 12% chance 4 - 12% chance 5 - 10% chance 6 - 10% chance 7 - 8% chance 8 - 8% chance 9 - 5% chance 10 - 5% chance

How would I go about coding this up in PHP?

Improve this question
1
  • You could use a standard distribution (gaussian) algorithm with a mean at 1, but ChristopheD's answer is far more simple. Commented May 11, 2012 at 21:56

4 Answers 4

Reset to default
4

I assume your percentages add up to 100%?

Build an array with 

15 times a '1' value, 15 times a '2' value, ... 10 times a '6' value, 8 times a '7' value, ... 5 times 1 '10' value

You'll end up with a single array which contains 100 elements.

Pick an element randomly (and pop it from the array).

Improve this answer
Sign up to request clarification or add additional context in comments.

5 Comments

Is there a mathematical way to do this though without the array overhead? How would we code up something that was from 1-100,000.
making an array like that seems excessive and it will not support weights like 10.5%
@yamikoWebs: if you need a resolution of 0.5% instead of 1% for the weighing, you just need a 200 element array ;-) To me this looks like a good (simple) fit for the question at hand imho, I was certainly not claiming the definite solution to every possible variation on this theme...
@ChristopheD I dont like the idea of making an array that large if it isn't necessary. btw I added a class that I think is more efficient/maintainable this as an answer...its been at the bottom because Ive been editing it a lot for improvement...plan on updating it to allow it to return values other than strings and whole numbers by using a multidimensional array but not today :P
The array solution allows you to pick your random choices in O(1) at the expense of O(N) space. You could do the opposite compromise, by just storing a list of the choices, with their weights, and iterating through them to get the correct one (this is Mala's solution). Both of these methods have important drawbacks. The solution which you are looking for is called the "Alias method". This has been discussed several times on StackOverflow. There is an implementation in Python that's on Google, if you're interested.
1

an example echoing value with OPs weight with the below class:

echo 1+Rand::get_weighted_rand(array(15,15,12,12,10,10,8,8,5,5));

and the class:

class Rand { /* * generates a random value based on weight * @RETURN MIXED: returns the key of an array element * @PARAM $a ARRAY: * the array key is the value returned and the array value is the weight * if the values sum up to less than 100 than the last element of the array * is the default value when the number is out of the range of other values * @PARAM $p INT: number of digits after decimal * * i.e array(1=>20, 'foo'=>80): has an 80 chance of returning Foo * i.e array('bar'=>0.5, 2=>1, 'default'=>0), 1: 98.5% chance of returning default */ public static function get_weighted_rand($a, $p=0) { if(array_sum($a)>100) return FALSE;#total must be less than 100 $p=pow(10, $p+2); $n=mt_rand(1,$p)*(100/$p); $range=100; foreach($a as $k=>$v) { $range-=$v; if($n>$range) return $k; } #returning default value end($a); return key($a); } }
Improve this answer

Comments

1

If your weights are in percentages, pick a random number between 0 and 100, then iteratively subtract the percentages until you cross zero:

<?php function getWeightedRandom() { $weights = array(15, 15, 12, ...); // these should add up to 100 $r = rand(0, 99); for ($i=0; $i<count($weights); $i++) { $r -= $weights[$i]; if ($r < 0) return $i+1; } } ?>

This has the added benefit of supporting non-integer weights.

Improve this answer

4 Comments

Doesn't work if values have equal weights, imagine $weights as an array of 10 times 10. You'd always get the first value. Also depends on $weights to be sorted (descending).
Actually it does work with equal-weighted values, $weights does not need to be sorted (the range [0 - 0.2] is exactly as likely as the range [0.8 - 1])...
Yes, but you return on the first value that meets $r < 0. Imagine $weights = array(1, 90, 9);. Your loop iterates 1 as the first element, and it has only a 2% chance of NOT returning. ($r = 0 or $r = 1) (eg. 98% of the time you'd have the key with the 1% probability in this example)
You are correct in that there is a small percent chance the function does not return (although it's slightly less than 1%, when $r is 100), but you are wrong in that it it returns the elements with the correct probabilities. I encourage you to actually try the code with your own example. The function failing to return slightly less than 1% of the time) is fixed by changing $r to be between 0 and 99 (which yields 100 possibilities)
0

Put them all multiple times in array, e.g. the 1 15 times, the 3 12 times and so on. Then pick a random number from that array.

$array = array_merge (array_fill (0, 15, 1), array_fill (0, 15, 2), array_fill (0, 12, 3), array_fill (0, 12, 4), array_fill (0, 10, 5), array_fill (0, 10, 6), array_fill (0, 8, 7), array_fill (0, 8, 8), array_fill (0, 5, 9), array_fill (0, 5, 10)); $random_number = array_rand ($array);
Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.