Basically you do a reverse fisher yates shuffle. You are selecting n of N items, where N is unknown, in one pass, where every item is treated as unique, and wh

Basically you do a reverse fisher yates shuffle. You are selecting n of N items, where N is unknown, in one pass, where every item is treated as unique, and where n is your sample size. First get n items from N in an array of size n of candidates, which we'll call C. Then, for each item k in N until you reach the end you know the current highest count, so select a random integer representing a location in an array of that count. If it's 0 to n - 1 (assuming a zero indexed array) replace the item in C with the current item k. This means that each item will have an equal chance of being a final candidate when you reach N. If you care about order of the random sample, you can always shuffle n after you reach N.