Given a list of length n select k random elements using C#

.net, algorithm, c#

Solution

I would suggest simply shuffling elements as if you were writing a modified Fisher-Yates shuffle, but only bother shuffling the first `k` elements. For example:

public static void PartialShuffle<T>(IList<T> source, int count, Random random)
{
    for (int i = 0; i < count; i++)
    {
        // Pick a random element out of the remaining elements,
        // and swap it into place.
        int index = i + random.Next(source.Count - i);
        T tmp = source[index];
        source[index] = source[i];
        source[i] = tmp;
    }
}

After calling this method, the first `count` elements will be randomly picked elements from the original list.

Note that I've specified the `Random` as a parameter, so that you can use the same one repeatedly. Be careful about threading though - see my article on randomness for more information.

Problem

I found this post: Efficiently selecting a set of random elements from a linked list But this means that in order to approach true randomness in the sample I have to iterate over all elements, throw them in memory with a random number, and then sort. I have a very large set of items here (millions) - is there a more efficient approach to this problem?

Original source

Related problems