Knuth's algorithm S: Difference between revisions

#* Select the first n items as the sample as they become available;

#* For the i-th item where i > n, have a random chance of n/i of keeping it. If failing this chance, the sample remains the same. If not, have it randomly (1/n) replace one of the previously selected n items of the sample.

#* Repeat #2 for any subsequent items.

#* Create a function <code>s_of_n_creator</code> that given <math>n</math> the maximum sample size, returns a function <code>s_of_n</code> that takes one parameter, <code>item</code>.

#* Function <code>s_of_n</code> when called with successive items returns an equi-weighted random sample of up to n of its items so far, each time it is called, calculated using Knuths Algorithm S.

#* Test your functions by printing and showing the frequency of occurrences of the selected digits from 100,000 repetitions of: