View Single Post
Nov27-10, 12:46 AM
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...