View Single Post
Nov26-10, 11:46 PM
P: 115
Quote Quote by CRGreathouse View Post
I assume you mean k/n, not 1/n.

Yes -- but it won't be efficient. Store the first k items as your preliminary picks. Start x as k + 1 and increase it by 1 until you reach the end of the file. For each x, select x with probability k/x. If selected, choose a random number r from 1 to k and replace preliminary pick r with x.
What happens if k > n? That to me is the problem...