How To Make A Weighted Selection?

What I currently have is something like this:

colors = {"Red","Blue","Yellow"}
selected = colors[math.random(1,#colors)]

How would I make it so that the ones that aren't selected receive a higher "weight" making it more likely they are selected next?

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