# Difference between revisions of "TADM2E 2.43"

A solution for the known $S$ size: While $S'$ size is less than $k$, look at the first element of $S$. For each iteration, calculate the probability of admitting the element from $S$ into $S'$ as $\frac{k - \text{size}(S')}{\text{size}(S)}$, and admit elements accordingly. Each step, remove the first element from $S$, and update the probability ratio accordingly.
Whether we know $n$ or not we can sample $k$ values uniformly by assigning a random value to each element, sorting, and taking the top $k$ values. However, this is not very efficient so instead we can use a priority queue of size $k$ with random priority.
Alternatively, we can iterate over the elements in $S$ from $i = 0$ until $S[i]$ is empty. If $i < k$, $S'[i] = S[i]$. After that, for each $i$, replace a random element in $S'$ with $S[i]$, with probability $\frac{k}{i + 1}$ of performing the replacement rather than skipping to the next.