11

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

4
  • possible duplicate of Five unique, random numbers from a subset
    – Tim Stone
    Nov 28, 2010 at 21:29
  • 1
    @drachenstern: Bit touchy today aren't we? @Tim - Sorry, I didn't search for 'subset' keyword and ended up with results for why random number generation is hard. Thanks for the link.
    – Skoder
    Nov 28, 2010 at 21:34
  • ~ I don't think so. I think this problem is well solved. Somebody else apparently agrees with me.
    – jcolebrand
    Nov 28, 2010 at 21:41
  • 1
    @drachenstern - Nothing to do with what you were saying. Just wondering if sarcasm was really required.
    – Skoder
    Nov 28, 2010 at 21:43

7 Answers 7

17

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

5
  • @HPT: Naturally in that case it is better to keep a set of already had numbers. But in this case, when the numbers are small, I believe my solution is not bad at all Nov 28, 2010 at 21:32
  • 2
    @armen: Correct solution is something and good solution is another thing. you can write a random generator as question mentioned for this problem too! but that could not be the solution.
    – user415789
    Nov 28, 2010 at 21:39
  • @HPT: At least my solution has predictable runtime Nov 28, 2010 at 21:41
  • 1
    @at least O(n) memory usage and O(n) runtime! n : indicates the range
    – user415789
    Nov 28, 2010 at 22:02
  • 1
    This solution may be okay for 6-from-50 since random-sorting 50 items may not not be a killer. But, then again, so is the simplistic remember-and-throw-away-duplicates method since the chances of duplicates is not high. For a more efficient answer (no upfront sorting, guaranteed no duplicates), you want Fisher-Yates shuffle as per my answer but that may not actually be necessary here - you have to target your solutions to the problem.
    – paxdiablo
    Nov 28, 2010 at 22:08
11

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.

2
  • This is the best solution, an improved version of mine. Nov 29, 2010 at 1:12
  • Storing all numbers in memory may be impossible if the range is huge Aug 4, 2015 at 20:54
8
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];
1
  • First one is a very neat solution. Thank you!
    – Chris Rae
    Feb 6, 2017 at 18:46
6

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.

3
  • 2
    Removing the number from the List (whatever IEnumerable you want to use) makes it unique, you can't get it from the list if it doesn't exist... Again this is faster for LARGE sets of unique numbers, because you are not looking for a number that may or may not exist. Nov 28, 2010 at 21:34
  • 1
    works great for me. Just one minor bug: it should be uniqueInts.RemoveAt(index); instead of uniqueInts.Remove(index);
    – AyKarsi
    Nov 11, 2011 at 10:07
  • @AyKarsi, That is an extremely important note, thanks! (Updated) Nov 11, 2011 at 18:23
1

instead of using List use Dictionary!!

2
  • also you should check to add N successful add, It's obvious how to check whether you have added a new value to dictionary or not!
    – user415789
    Nov 28, 2010 at 21:31
  • Thanks for the tip. I guess dictionaries would be better for larger sets.
    – Skoder
    Nov 28, 2010 at 21:32
0

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;
            }
        }
    }
-1

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

1
  • 6
    Dreadfully inefficient solution... especially when there have been much better answers already presented. You also got unused properties and you used Goto!!! Why?
    – bPratik
    Oct 14, 2012 at 19:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.