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]).