Random Sample

wiki

Problem 24: Draw N different random numbers from the set 1..M

We give a solution here in Lua. This solution shows some of the power of Lua's metatable protocol to implement a lazy table technique.

The general solution is also pretty simple: construct the vector 1..M; do a random permutation; and return the first N values. Of course, we don't need to do the entire random permutation; we can stop after N values.

The random permutation is straightforward:

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

So we could just construct the vector 1..M and use the above function. But what if M were quite large, relative to N? At most we're going to touch 2N elements of the table. If N were 6 and M were 1,000 -- or worse, if N were 1,000 and M were 1,000,000 -- it would be seriously inefficient to construct 1..M

Suppose, instead, we just make a table that looks like it contains 1..M. In fact, we can make a table that looks like it contains 1..∞:

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

Now we can go ahead and solve the original problem:

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

The approach used here is a type of lazy evaluation [wikipedia], which we might here call a lazy table (a bit related to the Haskell lazy list). It's vaguely related to the technique of memoisation (see FuncTables and [wikipedia]).