# Random Sample  wiki

The following problem is taken from [99 Lisp Problems]:

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..&#X221E;`:

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

RecentChanges · preferences
edit · history
Last edited January 16, 2007 1:02 pm GMT (diff)