随机样本

wiki

问题 24：从集合 1..M 中随机抽取 N 个不同的数字

我们在这里给出一个 Lua 的解决方案。这个解决方案展示了 Lua 元表协议在实现惰性表技术方面的强大功能。

一般的解决方案也很简单：构造向量 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

这里使用的方法是一种惰性求值 [维基百科]，我们这里可以称之为惰性表（与 Haskell 的惰性列表有点关系）。它与记忆化技术有点关系（参见 FuncTables 和 [维基百科]）。