How To Make A Weighted Selection?

Two questions asking a very similar question:

• https://scriptinghelpers.org/questions/9438/randomly-select-player

• https://scriptinghelpers.org/questions/4530/percentage-based-probability-selection

math.random() only returns uniform numbers between 0 and 1.

If you wanted equal weight to each choice, you would split it up like this:

(using 4 for convenience)

[ 0, 0.25 ) Red
[ 0.25, 0.5 ) Green
[ 0.5, 0.75 ) Yellow
[ 0.75, 1 ) Blue

So this makes it somewhat clear what we have to do. We make this intervals bigger or smaller to make it more likely to be picked. If we wanted Green to be twice as likely as any other, we could solve

-- Math, not Lua
G = R * 2
G + R * 3 = 1

So G = 0.4 and R = 0.2

[ 0, 0.2 ) Red
[ 0.2, 0.6 ) Green
[ 0.6, 0.8 ) Yellow
[ 0.8, 1 ) Blue

In general, making these values sum up to 1 would be difficult. Instead, we can pick them arbitrarily, not caring what they add up to.

We add them all up to get a total, and instead of generating numbers on [0, 1) we generate them on [0, total) = [0, 1) * total.

local choices = { "Red","Blue", "Yellow" }
local weights = { 1 , 2 , 3 } -- Yellow is 50% more likely than Blue
-- Yellow will be picked half the time,
-- and Red will be picked one third of the other half (1/6 overall)

local totalWeight = 0
for _, weight in pairs(weights) do
    totalWeight = totalWeight + weight
end

rand = math.random() * totalWeight
choice = nil

for i, weight in pairs(weights) do
    if rand < weight then
        choice = choices[i]
        break
    else
        rand = rand - weight
    end
end

print(choice)

So now that we can select an item randomly, we just need to update the weights to reflect more likely choosing ones which haven't been chosen recently.

A simple way to do this is to start all the weights at some number (e.g., 1) and each time they are not chosen, increase their weight by 1. Every time they are chosen, reset the weight to the starting value:

function chooseValue()
    for i = 1, #weights do
        weights[i] = weights[i] + 1
        -- Make everything more likely to be picked
        -- (accumulates between random choices)
    end

    -- Sum all weights
    local totalWeight = 0
    for _, weight in pairs(weights) do
        totalWeight = totalWeight + weight
    end

    -- Pick random value
    rand = math.random() * totalWeight
    choice = nil

    -- Search for the interval [0, w1] [w1, w1 + w2] [w1 + w2, w1 + w2 + w3 ] ....
    -- that `rand` belongs to
    -- and select the corresponding choice
    for i, weight in pairs(weights) do
        if rand < weight then
            choice = choices[i]
            weights[i] = 1 -- Reset weight to small value
            break
        else
            rand = rand - weight
        end
    end

    return choice
end