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