隨機範例

wiki

問題 24：從 1..M 集合中抽出 N 個不同的隨機數字

我們在此以 Lua 提供一個解法。此解法展示了一些 Lua 元資料協定的功能，以實作一個惰性表格 technique.

一般解法也很簡單：建構向量 1..M；進行隨機排列；並傳回前 N 個值。當然，我們不需要進行整個隨機排列；我們可以在 N 個值後停止。

隨機排列很簡單

function permute(tab, n, count)
  n = n or #tab
  for i = 1, count or n do
    local j = math.random(i, n)
    tab[i], tab[j] = tab[j], tab[i]
  end
  return tab
end

因此我們可以僅建構向量 1..M 並使用上述函式。但是如果 M 相對於 N 而言相當大怎麼辦呢？我們最多會存取表格中的 2N 個元素。假設 N 為 6 而 M 為 1,000 -- 或更糟的情況，如果 N 為 1,000 而 M 為 1,000,000 -- 建構 1..M 會很不有效率

反過來說，假設我們只建立一張看起來像是包含 1..M 的表格。事實上，我們可以建立一張看起來像是包含 1..∞ 的表格

do
  local meta = {}
  function meta:__index(k) return k end
  function PositiveIntegers() return setmetatable({}, meta) end
end

現在我們可以繼續解決原始問題

function lotto(count, range)
  return {unpack(
               permute(PositiveIntegers(), range, count),
               1, count)
            }
end

此處使用的途徑是一種 惰性評估 [wikipedia]，我們在此稱之為 惰性表格（有點類似 Haskell 的 惰性清單）。它與記憶化技術（見 FuncTables 和 [wikipedia]）有一些關聯。