Weighted random choice enables you to select a random value out of a set of values while influencing the chance that any given value is chosen. I've used this to create a playlist generator that works as follows:

• Take the last track in the playlist and look for related artists on Last.fm
• Find all tracks in the user's library by one of the related artists
• Increase the weight of favorite tracks and tracks by favorite artists
• Decrease the weight of tracks by the last ten artists in the playlist (to prevent loops)
• Use weighted random choice to select a track to add to the playlist

If you're familiar with Music Player Daemon you might be interested in mpd-myfm which implements this idea in Python.

Author: Peter Odding

### Snippet

```--[[

The `choices' table contains pairs of
associated (choice, weight) values:

{ Lua = 20, Python = 10, Perl = 5, PHP = 2 }

--]]

function weighted_random_choice(choices)
local threshold = math.random(0, weighted_total(choices))
local last_choice
for choice, weight in pairs(choices) do
threshold = threshold - weight
if threshold <= 0 then return choice end
last_choice = choice
end
return last_choice
end

function weighted_total(choices)
local total = 0
for choice, weight in pairs(choices) do
total = total + weight
end
end```

Tests/Usage

```--[[

Sample output:

Lua: expected 54%, result is 51%
Python: expected 27%, result is 26%
Perl: expected 13%, result is 13%
PHP: expected  5%, result is  8%

--]]

local choices = { Lua = 20, Python = 10, Perl = 5, PHP = 2 }
local results = {}
local iterations = 1000
for i = 1, iterations do
local choice = weighted_random_choice(choices)
results[choice] = (results[choice] or 0) + 1
end
local expected_total = weighted_total(choices)
local actual_total = 0
for choice, weight in pairs(results) do
actual_total = actual_total + weight
end
local function printf(s, ...)
io.write(s:format(...), '\n')
end
for _, choice in ipairs { 'Lua', 'Python', 'Perl', 'PHP' } do
local expected = choices[choice] / (expected_total / 100)
local actual = results[choice] / (actual_total / 100)
printf('% 8s: expected %2i%%, result is %2i%%',
choice, expected, actual)
end```

Related Snippets

Revision 000003 by Peter Odding; created Sat, 08 Jan 2011 17:11:59 +0000