Generate N random and unique numbers within a range

Question

What is an efficient way of generating N unique numbers within a given range using C#? For example, generate 6 unique numbers between 1 and 50. A lazy way would be to simply use Random.Next() in a loop and store that number in an array/list, then repeat and check if it already exists or not etc.. Is there a better way to generate a group of random, but unique, numbers? To add more context, I would like to select N random items from a collection, using their index.

thanks

Answer 1

var random = new Random();
var intArray = Enumerable.Range(0, 4).OrderBy(t => random.Next()).ToArray();

This array will contain 5 random numbers from 0 to 4.

or

  var intArray = Enumerable.Range(0, 10).OrderBy(t => random.Next()).Take(5).ToArray();

This array will contain 5 random numbers between 0 to 10.

int firstNumber = intArray[0];
int secondNumber = intArray[1];
int thirdNumber = intArray[2];
int fourthNumber = intArray[3];
int fifthNumber = intArray[4];

Answer 2

Take an array of 50 elements: {1, 2, 3, .... 50} Shuffle the array using any of the standard algorithms of randomly shuffling arrays. The first six elements of the modified array is what you are looking for. HTH

Answer 3

For 6-from-50, I'm not too sure I'd worry about efficiency since the chance of a duplicate is relatively low (30% overall, from my back-of-the-envelope calculations). You could quite easily just remember the previous numbers you'd generated and throw them away, something like (pseudo-code):

n[0] = rnd(50)
for each i in 1..5:
    n[i] = n[0]
while n[1] == n[0]:
    n[1] = rnd(50)
while n[2] == any of (n[0], n[1]):
    n[2] = rnd(50)
while n[3] == any of (n[0], n[1], n[2]):
    n[3] = rnd(50)
while n[4] == any of (n[0], n[1], n[2], n[3]):
    n[4] = rnd(50)
while n[5] == any of (n[0], n[1], n[2], n[3], n[4]):
    n[5] = rnd(50)

However, this will break down as you move from 6-from-50 to 48-from-50, or 6-from-6, since the duplicates start getting far more probable. That's because the pool of available numbers gets smaller and you end up throwing away more and more.

For a very efficient solution that gives you a subset of your values with zero possibility of duplicates (and no unnecessary up-front sorting), Fisher-Yates is the way to go.

dim n[50]                 // gives n[0] through n[9]
for each i in 0..49:
    n[i] = i              // initialise them to their indexes
nsize = 50                // starting pool size
do 6 times:
    i = rnd(nsize)        // give a number between 0 and nsize-1
    print n[i]
    nsize = nsize - 1     // these two lines effectively remove the used number
    n[i] = n[nsize]

By simply selecting a random number from the pool, replacing it with the top number from that pool, then reducing the size of the pool, you get a shuffle without having to worry about a large number of swaps up front.

This is important if the number is high in that it doesn't introduce an unnecessary startup delay.

For example, examine the following bench-check, choosing 10-from-10:

<------ n[] ------>
0 1 2 3 4 5 6 7 8 9  nsize  rnd(nsize)  output
-------------------  -----  ----------  ------
0 1 2 3 4 5 6 7 8 9     10           4       4
0 1 2 3 9 5 6 7 8        9           7       7
0 1 2 3 9 5 6 8          8           2       2
0 1 8 3 9 5 6            7           6       6
0 1 8 3 9 5              6           0       0
5 1 8 3 9                5           2       8
5 1 9 3                  4           1       1
5 3 9                    3           0       5
9 3                      2           1       3
9                        1           0       9

You can see the pool reducing as you go and, because you're always replacing the used one with an unused one, you'll never have a repeat.

Using the results returned from that as indexes into your collection will guarantee that no duplicate items will be selected.

Answer 4

For large sets of unique numbers, put them in an List..

        Random random = new Random();
        List<int> uniqueInts = new List<int>(10000);
        List<int> ranInts = new List<int>(500);
        for (int i = 1; i < 10000; i++) { uniqueInts.Add(i); }

        for (int i = 1; i < 500; i++)
        {
            int index = random.Next(uniqueInts.Count) + 1;
            ranInts.Add(uniqueInts[index]);
            uniqueInts.RemoveAt(index);
        }

Then randomly generate a number from 1 to myInts.Count. Store the myInt value and remove it from the List. No need to shuffle the list nor look to see if the value already exists.