Generating Distinct, Random Array Indices

I wrote an article titled “Generating Distinct, Random Array Indices” that was published in the July 2013 issue of Visual Studio Magazine. See This isn’t an earth-shattering topic, but it is a common task that I hadn’t seen explained in print before. The problem to solve is this: suppose you have an array of size 100 which has 0-based indices from 0 to 99. You want to select a subset of 5 the values in the array. To do this you can generate 5 random indices, for example, 3, 17, 44, 67, and 92, and then access the values in the array at those indices. So how do you select 5 indices between 0 and 99 without getting any duplicates?

In the article I describe three techniques: a brute-force approach, an approach based on the Fisher shuffle algorithm, and an approach based on a very clever idea called reservoir sampling. I demonstrate how to use each technique in a short C# program.


This entry was posted in Machine Learning, Software Test Automation. Bookmark the permalink.