Category: Random

Given an infinite stream (or a finite sequence of size n), choose k numbers randomly.

Generating a random permutation of a finite sequence. O(n^2) The basic method given for generating a random permutation of the numbers 1 through N goes as follows: Write down the numbers from 1 through N. Pick a random number k between one and the number of unstruck numbers remaining (inclusive). Counting from the low end, strike out the kth number not…