I’d like to share with you a simple algorithm for taking random selections from a set of items while factoring in a manual, arbitrary “weighting” mechanism.

We’re assuming that the default weight is 1, and that a weight of 0 would exclude an item from the result set. Whether or not there is a “maximum” weight is irrelevant to this algorithm.

The idea is that you first sum all of the weights together, to get a grand total of the combined weight of all items in the result set. Now imagine all of your results lined up in a straight line, with the size of their spot in the line determined by their weight. So if the first item has a weight of 50, its spot in line goes from points 1 to 51. If the second item has a weight of 20, it goes from points 52 to 72. And so on, with the last item ending at that cumulative total we calculated.

What you then do is pick random numbers between (and including) 1 and that cumulative total. Whatever item is occupying that position in the line is your winner. Repeat for as many results as you need.

If your data is in a MySQL database, you can add a running cumulative count to the results array using a MySQL variable:

SET @csum := 0;
SELECT
	item.id,
	item.name,
	item.field,
	item.weight,
	(@csum := @csum + item.weight) as cumulative_sum
FROM items as item
WHERE item.weight > 0
ORDER BY id;

Then you iterate through a loop for as many random selections as you need, counting up to the item whose cumulative_sum contains your random number. For example, in PHP:

$winners = array();
while ($has_enough == false) {
	$random_index = rand(1,$cumulative_total);
	foreach ($items as $item) {
		if ($item['cumulative_sum'] >= $random_index) {
			$winners[] = $item;
			// Set $has_enough to true when you have enough...
			break;
		}
	}
}

All in all, very efficient.


Comments

0
There are no comments.