Random Sample 

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