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

For when you want to select few numbers from a huge range, modify the Fisher-Yates shuffle to track the indexes that were swapped instead of storing the entire array of possibilities. This reduces the memory usage to O(numValues). This will be much more efficient when numValues ≪ maxValueExclusive, but still deterministically terminates.

public static int[] GetUnique(Random rng, int numValues, int maxValueExclusive)
{
    if (maxValueExclusive < numValues)
    {
        throw new ArgumentOutOfRangeException(nameof(maxValueExclusive),
            string.Format("Cannot select {0} unique values from a set containing {1} values", numValues, maxValueExclusive));
    }

    int[] result = new int[numValues];
    Dictionary<int, int> valueMap = new();
    for (int i = 0; i < numValues; ++i)
    {
        var randVal = rng.Next(maxValueExclusive);
        result[i] = valueMap.GetValueOrDefault(randVal, randVal);
        if (randVal != --maxValueExclusive)
            valueMap[randVal] = valueMap.GetValueOrDefault(maxValueExclusive, maxValueExclusive);
    }
    return result;
}

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

In case it helps anyone else, I prefer allocating the minimum number of items necessary. Below, I make use of a HashSet, which ensures that new items are unique. This should work with very large collections as well, up to the limits of what HashSet plays nice with.

    public static IEnumerable<int> GetRandomNumbers(int numValues, int maxVal)
    {
        var rand = new Random();
        var yieldedValues = new HashSet<int>();

        int counter = 0;
        while (counter < numValues)
        {
            var r = rand.Next(maxVal);
            if (yieldedValues.Add(r))
            {
                counter++;
                yield return r;
            }
        }
    }

Answer 4

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 5

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.

Answer 6

generate unique random nos from 1 to 40 :

output confirmed :

class Program

{
    static int[] a = new int[40];
    static Random r = new Random();
    static bool b;
    static void Main(string[] args)
    {
        int t;
        for (int i = 0; i < 20; i++)
        {
        lab:  t = r.Next(1, 40);
            for(int j=0;j<20;j++)
            {

                if (a[j] == t)
                {
                    goto lab;
                }
            }

            a[i] = t;
            Console.WriteLine(a[i]);



        }
        Console.Read();
    }


}

sample output :

7 38 14 18 13 29 28 26 22 8 24 19 35 39 33 32 20 2 15 37

Answer 7

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 8

instead of using List use Dictionary!!