What is the best way to efficiently extract a small random subset of a large enumeration?

Question

What is the best way to grab n items from an IEnumerable<T> in random order?

I'm writing a store API and need to provide a small set of random items from a sometimes huge enumeration of items. The underlying enumerable is sometimes an array, and sometimes a lazy evaluated filter of said array.

Since I'm just grabbing a proportionally small number of items from the enumerations, it is better to use some sort of repeatedly random index into the enumeration and dupe check every time rather than randomly sort the entire list using an existing algorithm and grab top x, right?

Any better ideas?

Answer 1

In another answer I provided a way of returning a single random element from a sequence, using just a single pass.

I suspect this could be adjusted reasonably easily to use a circular buffer and select a random sequence of a given size, but you'd have to be fairly careful to get the probabilities balanced.

Answer 2

If you use Knuthe Shuffle, it is possible to do a random shuffle on just part of the list. So, it is not necessary to sort an entire list just to get n random items. I do not know if this can be done efficiently within your constraints since you'll still need to convert what you are grabbing into a list before you can apply the algorithm.

In essence, the strategy is to grab a random item, swap it with the first item of the list. The next time you need a random element, skip the first one.

Answer 3

If you know the number of items in advance, it's fairly trivial to calculate n random numbers within that range, and then grab those with these indexes.