Weighted Random

PHP programming forum. Ask questions or help people concerning PHP code. Don't understand a function? Need help implementing a class? Don't understand a class? Here is where to ask. Remember to do your homework!

Moderator: General Moderators

Post Reply
Pezmc
Forum Commoner
Posts: 53
Joined: Mon Nov 06, 2006 2:15 pm

Weighted Random

Post by Pezmc »

I have a mysql query querying my database using order by RAND() LIMIT 1 to sellect a random coice from the database, however I would like to have the chance of a object being chosen increased for certain values (Weighting?)

In my database I have:

Code: Select all

id  name weight
1  Pezm  1
2  Shog  1.1
3  Ebay  1.2
4  PLp   1.3
5  php  1.4
So follwing the information in my database if a weighted random script is used php shuld be the most frequent with 1.4*the chance to get chosen, compared to Pezm,

How can this be acchieved?
User avatar
feyd
Neighborhood Spidermoddy
Posts: 31559
Joined: Mon Mar 29, 2004 3:24 pm
Location: Bothell, Washington, USA

Post by feyd »

User avatar
pickle
Briney Mod
Posts: 6445
Joined: Mon Jan 19, 2004 6:11 pm
Location: 53.01N x 112.48W
Contact:

Post by pickle »

Since RAND() can accept a variable, I'm wondering if it would be possible to put the `weight` field as the argument. That way, the higher the weight, the higher a possible number could be:

Code: Select all

SELECT
  *
FROM
  myTable
ORDER BY
  RAND(weight)
Real programmers don't comment their code. If it was hard to write, it should be hard to understand.
User avatar
Mordred
DevNet Resident
Posts: 1579
Joined: Sun Sep 03, 2006 5:19 am
Location: Sofia, Bulgaria

Post by Mordred »

You make an accumulative sum of weights for each item, then normalise the random by multyplying by the total sum of weights.

Here's a quick hack (without the LIMIT 1 which you'll also need), with the accumulative sum and total sum also shown as columns (you don't really need them).

The heart of it is the rand()*total_sum >= accumulated sum. The sum is also accumulated backwards, so we can choose the topmost result instead of the bottommost.

Code: Select all


CREATE TABLE `rand` (
  `id` int(11) NOT NULL auto_increment,
  `item` varchar(255) NOT NULL default '',
  `weight` float NOT NULL default '0',
  UNIQUE KEY `id` (`id`)
) ENGINE=MyISAM  DEFAULT CHARSET=latin1 AUTO_INCREMENT=5 ;


INSERT INTO `rand` (`id`, `item`, `weight`) VALUES 
(1, 'item 1', 1),
(2, 'item 2', 2.5),
(3, 'item 3', 1.3),
(4, 'item 4', 0);

SELECT * , (

SELECT sum( weight ) 
FROM `rand` AS t_sum
WHERE t_sum.id >

t.id
) AS weight_sum, (
SELECT sum( weight ) 
FROM `rand` 
) AS weight_total
FROM `rand` AS t
WHERE weight !=0
AND rand( ) * ( 
SELECT SUM( weight ) 
FROM `rand` ) > = ( 
SELECT sum( weight ) 
FROM `rand` AS t_sum
WHERE t_sum.id >

t.id ) ORDER BY t.id ASC
Post Reply