使用鍵值對數組構造的無重覆隨機數演算法

-- @param list_length 生成的數組長度
-- @param max_random_length 隨機數的最大範圍
math.generate = function (list_length, max_random_length)
	local random = {}
	local random_list = {}

	-- 輸出隨機數表, 通過判斷是否存在隨機數鍵避免重覆隨機數
	for i = 1, list_length do
		local random_number = math.random(1, max_random_length)
    -- 當存在該隨機數時, 重覆隨機至不重覆
		while random[random_number] do
			random_number = math.random(1, max_random_length)
		end
		random[random_number] = true
	end

	for key, value in pairs(random) do
		table.insert(random_list, key)
	end

	return random_list
end

在上面的函數math.generate中, 需要傳入兩個參數: 隨機數表的長度list_length和最大隨機數max_random_length. 返回1個沒有重覆值的隨機數表.

由於lua的table本質上是鍵值對動態數組, 所以(line 14)可以直接將隨機出來的數字random_number傳入key中, 這樣就表示這個隨機數已經有了, 後續再隨機出相同的隨機數就會進入(line 11)的迴圈中去再次隨機.

這樣做的好處是, 不用和按順序填充隨機數表時, 每隨機出一個值就需要和前面的所有值進行遍歷查詢, 這種隨機數生成方式只需要比對一次就知道是否重覆, 極大減少了時間複雜度.

最後, 通過pairs迭代器遍歷出random所有的鍵(隨機數)就構成了一個新的無重覆隨機數組random_list.