Let $M$ be a collection of elements given in the form of the array such that membership of any element can be done in $O(1)$ time. Which means elements of array $M$ are $\{1,2,\cdots,n\}$ such that $1$ is stored at $M[1]$ and $2$ at $M[2]$ and so on. The goal is to sample an element from the array $M$.
Note that we have to design an algorithm multiple times (say $k$ times) in such a way that in each repetition we get a different element as a result.
Sampling means the probability of picking any element from $M$ is $\frac{1}{|M|}$.
My idea is as follows: create another array $F:=[\frac{1}{|M|},\frac{1}{|M|},\cdots,\frac{1}{|M|}]$, which means assigning equal weights to each element.
There are several existing algorithms now which can sample an element from $M$ in expected time $O(1)$ (Say Algorithm 1 Algorithm).
If I run the same algorithm 1 again then the same element may get picked so I have to update something in the array $F$ this update should be in $O(1)$ time.
I am looking for an algorithm that gives $O(k)$ time for $k$ repetitions other than constructing array $F$.
How to modify the above algorithm such that next time I get a different answer?
EDIT: For any $a\in \{1,2,...,n\}, $Pr[Output_1=a] = $\frac{1}{|M|}$ and Pr[Output_i=a|Output_i-1 =a_i-1,...,Output_1=a_1]. Output_i denotes the output of the algorithm in the $i$th iteration and Pr denotes the probability.
