Previous Next

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

License: MIT/X11 Tags: random

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
  return total
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

• Shuffle array (1)

0 comments

Add a Comment