A fair sample from a stream

Choose k items fairly from stream, which can be read only once, item by item, and whose length is not known in advance. Use reservoir sampling exactly as lesson 7 describes, with the random function you are given:

• keep the first k items, in slots 0 to k − 1, in order;
• for each later item, the one at position i (counting from 0), call rand(i + 1) once to get j from 0 to i; if j < k, put the item in slot j.

Return the list of slots. If the stream has fewer than k items, return all of them. Do not call rand for the first k items.

# rand returns 1, 0, 3, 2 in turn
sample(iter("abcdef"), 2, rand)   # ['d', 'c']
sample(iter([7, 8]), 5, rand)     # [7, 8]

Limits

• The stream may be a generator: it has no len(), and it can be looped over only once. It has up to 300,000 items.
• The tests pass fixed “random” answers, so the right sample is known exactly. Two tests try every possible run of answers and check that every set of items is chosen equally often.