Select N random items from an array in C#

[Select N random items]

This example builds a generic extension method that lets you easily select N random objects from an array. For example, it lets you select 5 items from an array holding 10 names.

Picking one random item from an array is easy. Just use a Random object as demonstrated by the example Select random objects from an array in C#.

You can extend this idea a bit, but there are complications. For example, if you pick a second item randomly, what happens if you pick the same item again? The easiest solution would be to use the following item, but that would increase the odds of picking the following item (from 1 in N to 2 in N). And what if the item you picked twice is the last item so there is no following item? Things get even messier if you need to pick more items.

A better approach is to randomize the array of items and then pick the first N of them. In fact, you can save some time of you only randomize the first N items.

The following code shows a PickRandom extension method that does this and the RandomTools class that defines it.

public static class RandomTools
{
    // The Random object this method uses.
    private static Random Rand = null;

    // Return num_items random values.
    public static List<T> PickRandom<T>(
        this T[] values, int num_values)
    {
        // Create the Random object if it doesn't exist.
        if (Rand == null) Rand = new Random();

        // Don't exceed the array's length.
        if (num_values >= values.Length)
            num_values = values.Length - 1;

        // Make an array of indexes 0 through values.Length - 1.
        int[] indexes =
            Enumerable.Range(0, values.Length).ToArray();

        // Build the return list.
        List<T> results = new List<T>();

        // Randomize the first num_values indexes.
        for (int i=0; i<num_values; i++)
        {
            // Pick a random entry between i and values.Length - 1.
            int j = Rand.Next(i, values.Length);

            // Swap the values.
            int temp = indexes[i];
            indexes[i] = indexes[j];
            indexes[j] = temp;

            // Save the ith value.
            results.Add(values[indexes[i]]);
        }

        // Return the selected items.
        return results;
    }
}

The class first defines a private variable of type Random. It uses that object to generate random numbers when it needs them.

Next the class defines the PickRandom extension method. The <T> after the method’s name indicates that this is a generic method that takes one generic parameter that is called T within the method.

The this keyword indicates that this is an extension method that extends the variable that follows it. In this case, it extends an array of type T.

The method first checks the variable Rand and initializes it if it is null.

Next the code ensures that num_values isn’t larger than the array’s length. For example, you can’t select 10 items from an array containing 5 elements.

To make its selections, the method needs to randomize the items. But I don’t want to mess up the original ordering of the items. To avoid that, the method instead makes an array containing the indexes of the items and then randomizes part of that array. It can then use the randomized indexes to select items.

The algorithm calls the Enumerable.Range method to make a list of values between 0 and values.Length – 1. It calls the result’s ToArray method to convert the list into an array.

Next the code creates a List<T> to hold the method’s return values.

The code then enters a loop where i loops from 0 to num_values. For each value of i, the method picks a random array index between i and the end of the array. It then swaps the index in that position with the value in position i.

The code also adds the selected item to the results list. It uses the selected value in indexes[i] to pick the value from the original array of T.

After it has made all of its selections, the method returns the results list.

Note that this technique is similar to the one used by the example Make extension methods that randomize arrays and lists in C# except it stops when it has randomized enough items.

The following code shows how the main program uses this method.

// Pick some items.
private void btnPick_Click(object sender, EventArgs e)
{
    int num_values = int.Parse(txtNumSelections.Text);
    txtResults.Lines =
        txtNames.Lines.PickRandom(num_values).ToArray();
}

This code first gets the number of items to pick, num_values. It then uses the txtNames control’s Lines property to get the lines of text you entered in the TextBox on the left. It calls the PickRandom extension method for the array of lines to make the desired number of selections.

In this example, the result is a list of strings. The code calls its ToArray method to convert it into an array, and the saves it in the txtResults control’s Lines property so you can see the selections.


Download Example   Follow me on Twitter   RSS feed   Donate




This entry was posted in algorithms, arrays, mathematics, variables and tagged , , , , , , , , , , , , , . Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *