Test how much sorting of input influences weighted random choice

choice.lua

function choice(items)
	local total = 0
	for _, item in pairs(items) do total = total + item.weight end
	local threshold = math.random(0, total)
	for _, item in pairs(items) do
		threshold = threshold - item.weight
		if threshold <= 0 then return item.value end
	end
end

function sort(items, reverse)
	table.sort(items, function(a, b)
		if reverse then
			return a.weight < b.weight
		else
			return a.weight > b.weight
		end
	end)
	return items
end

function shuffle(items)
	for index, value in ipairs(items) do
		local newidx = math.random(1, #items)
		items[index] = items[newidx]
		items[newidx] = value
	end    
end

choices = {{ value = 'A', weight = 50 },
           { value = 'B', weight = 25 },
           { value = 'C', weight = 13 },
				   { value = 'D', weight = 6  },
				   { value = 'E', weight = 3  },
				   { value = 'F', weight = 2  },
				   { value = 'G', weight = 1  }}

sorted = {}
sorted_reverse = {}
shuffled = {}

samplesize = tonumber(arg[1]) or 1000

sort(choices, false)
for i = 1, samplesize do table.insert(sorted, choice(choices)) end

sort(choices, true)
for i = 1, samplesize do table.insert(sorted_reverse, choice(choices)) end

for i = 1, 10 do
	shuffle(choices)
	for i = 1, samplesize/10 do table.insert(shuffled, choice(choices)) end
end

for label, items in pairs { sorted=sorted, sorted_reverse=sorted_reverse, shuffled=shuffled } do
	counts = {}
	for _, v in pairs(items) do counts[v] = (counts[v] or 0) + 1 end
	io.write(label, ':\n')
	for _, value in ipairs { 'A', 'B', 'C', 'D', 'E', 'F', 'G' } do
		io.write(value, ': ', counts[value] / (#items / 100), '%\n')
	end
end

Output

peter@laptop:~$ lua choice.lua 10000
sorted_reverse:
A: 49.99%
B: 24.2%
C: 12.96%
D: 6.17%
E: 2.5%
F: 1.96%
G: 2.22%
shuffled:
A: 49.58%
B: 25.35%
C: 12.92%
D: 6.22%
E: 3.06%
F: 1.85%
G: 1.02%
sorted:
A: 49.99%
B: 25.17%
C: 12.74%
D: 5.95%
E: 3.35%
F: 1.76%
G: 1.04%