Random Sample

wiki

The problem is simple:

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

And the 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, range)
            }
end