Choose a uniformly random k-subset of [1,n] in O(k) time.

random_subset.lua

-- This returns a sequence of k distinct indexes in the range [1, n] chosen so
-- that, within the context of the pseudorandom generator, each k-subset has an
-- equal probability of being returned.
function random_indexes(k, n)
  -- This is a partial Fisher-Yates shuffle, as suggested by this answer:
  -- http://stackoverflow.com/a/29868630/3561
  local shuf    = {}
  local indexes = {}
  for i = 1, k do
    local j = math.random(i, n)
    shuf[i], shuf[j] = (shuf[j] or j), (shuf[i] or i)
    indexes[i] = shuf[i]
  end
  return indexes
end