Algorithm for sampling fixed number of samples from a finite population I'm looking for an algorithm that would do the following:
Imagine that you need to sample uniformly at random and without replacement $k$ elements from a pool of $n$ elements. The catch is that $n$ is unknown. You can iterate over the whole set of the elements, so eventually, you would learn $n$. The algorithm is ought to have $O(n)$ time complexity, you are allowed to iterate over the set only once. You are allowed to keep a small cache of size $m \approx k$, but memorizing all the elements is not possible as $n$ could be very large.
Example: you work at a factory, your job is to select exactly $k$  items from the production line for an inspection per day. You need to sample them uniformly at random (with a probability $k/n$ each). The problem is that the number of items produced by the production line is unpredictable, so you don't know if it would produce $k$ items, or $1,000k$ items, or a completely different number. You need to decide on the fly to keep an item or leave it, as they move over the production line and won't be available later.
This should be possible. I guess what I can do is to take the first $k$ samples that I saw, and on each following step with some probability $p$ drop one of the already available samples and take instead a new one. The probability of drawing a new sample would need to evolve over time, but also the probabilities of rejecting the already sampled values would change. Probability of rejecting $x_t$ would need to depend on time order when it was observed $t$. The first $k$ values were sampled with probability $1$, $k+1$ value would be sampled with probability $k/k+1$, the last value with probability $k/n$, etc. By rejecting items already collected we would "correct" the sampling probabilities.
I don't want to re-invent the wheel, so I wanted to ask if there already is an algorithm like this?

I think the most intuitive solution is that you have an ordered list, and every time you see a new item, you place the item into the list at a random location. Then you take the first $k$ elements of that list.
Since you're taking the first $k$ elements, you don't need to keep track of the elements after that, so you can instead maintain a list of length $k$. Each time you see a new item, if you had seen $m$ items previously, there's $m+1$ different places to put the new item, so each for each slot in the partial list, there's a $\frac 1 {m+1}$ probability of the new item going there, and a $\frac{m+1-k}{m+1}$ probability of it not going in the partial list at all. If it does go in a partial list, then item that was previously last in the list gets pushed out.
Since the order doesn't matter, you can simplify it even further by having each new item having probability $\frac k {m+1}$ of being added, and if it is added, then each old item has probability $ \frac 1 k$ being dropped.
This is the algorithm in whuber's answer (my $m+1$ is their $j$), but I think the explanation for it is more intuitive.
