How to select N random items from a list (Example)

azqjanna · November 16, 2022, 2:48am

I’ve seen a number of code examples that solve the problem described in the title. Given a list, such as the list of players in the game, you want to choose some number of them at random. Several solutions I have seen involve trial and error, selecting a random item in the list, making sure it hasn’t already been selected, and trying again if it has. I would like to show another solution to this problem.

--Create the identity set of length n
--[1] = 1
--[2] = 2
-- ...
--[n] = n
local function IdentitySet(n)
	local set = {}
	
	for i = 1, n do
		table.insert(set, i)
	end
	
	return set
end

--Scramble the items in a set by swapping them with a random other item
--Identical sets of the same length scrambled with the same seed will be identical
--Scramble only up to 'limit' items, saves time if only a small selection out of a very large set is needed
local function Scramble(set, seed, limit)
	limit = limit or #set
	math.randomseed(seed)
	
	for i = 1, limit do
		local j = math.random(1, #set)
		local temp = set[i]
		set[i] = set[j]
		set[j] = temp
	end
	
	return set
end

--Select 3 unique items out of 10, at random
local randomSelection = Scramble(IdentitySet(10), 12345, 3)

for i = 1, 3 do
	print(i .. ": " .. randomSelection[i])
end

--The first 3 numbers in randomSelection have been scrambled and are now random unique indexes
--You can ignore the other entries

This works because passing a non-random number through a random 1-to-1 mapping still results in a random selection. You can simply select any number of indices, even something like 1, 2, 3, and the resulting selection will be random and unique (no repeats).

The two functions here are also very useful for some other problems, such as randomly rearranging a list.

local length = #list
local rearrangeMapping = Scramble(IdentitySet(length), 12345)

local rearrangedList = {}
for i = 1, length do
	rearrangedList[rearrangeMapping[i]] = list[i]
end