Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

I want to generate a list of N different random numbers:

public static List<int> GetRandomNumbers(int count)
{
    List<int> randomNumbers = new List<int>(); 

    for (int i=0; i<count; i++) 
    {    
        int number;

        do number = random.Next();
        while (randomNumbers.Contains(number));

        randomNumbers.Add(number);
    }

    return randomNumbers;
}

But I feel there is a better way. This do...while loop especially makes this ugly. Any suggestions on how to improve this?

share|improve this question
2  
@MartinR Not exactly. Fisher–Yates shuffle gives you permutation of all elements in given range. –  Kao Aug 28 at 15:05
3  
@BrunoCosta: "so if the numbers don't repeat you can't actually call it random anymore, it will have the property of not repeating which is a very unique property": That's not true. "Random" does not imply "independent", let alone "not having any interesting properties". Heck, by your definition of "random", we couldn't even say "random integer", because the property of being an integer would mean it wasn't random . . . –  ruakh Aug 30 at 10:27
6  
Bob Floyd invented an algorithm for this purpose. See: stackoverflow.com/a/2394292/179910. It's substantially better than what you've shown or any of the answers currently posted. –  Jerry Coffin Sep 1 at 2:50
1  
@Kao - it would be great if we could discuss this question (and bounty) in chat... –  rolfl Sep 4 at 13:43
2  
@JerryCoffin , I believe I am correct, and that, for example, the first value in the result can never be N, which means that the randomness of the result is not maintained. The randomness of the selection is maintained, but the order is not random (enough). Can we clear this up in the 2nd Monitor? –  rolfl Sep 4 at 20:43

14 Answers 14

up vote 36 down vote accepted
+100

Updated answer in response to bounty: See Is that your final answer? at the end, and other changes - basically answer is significantly rewritten.


To break your problem down in to requirements:

  • you need a set of random numbers
  • the numbers need to be unique
  • the order of the returned numbers needs to be random

Your current code indicates that the range of random numbers is specified by Random.Next(), which returns values in the [0 .. Int32.MaxValue) range (note, it excludes Int32.MaxValue). This is significant for the purpose of this question, because other answers have assumed that the range is configurable, and 'small'.

If the range should be configurable, then the recommended algorithm would potentially be much larger.

Based on those assumptions, let's do a code review...

Code Style

do ... while

The most glaring problems here are the un-braced do-while loop. You already knew it, but this code is ugly:

    do number = random.Next();
    while (randomNumbers.Contains(number));

It really should be braced:

    do
    {
        number = random.Next();
    } while (randomNumbers.Contains(number));

This makes the statement clear, and significantly reduces confusion. Always use braces for 1-liners.

List Construction

The List class allows an initial capacity to be used. Since the capacity needs to just be count, it makes sense to initialize the list with this capacity:

List<int> randomNumbers = new List<int>(count);

Current Algorithm

This is where the most interesting observations can be made. Let's analyze your current algorithm:

  • Create a container for the results
  • repeat until you have selected N values:
    • Select a random value
    • check if it has been previously selected
    • if it is 'new', then add it to the container

This algorithm will produce random values, in a random order, and with good random characteristics (no skews, biases, gaps, etc.).

In other words, your results are good.

The problem is with performance....

There are two performance concerns here, one small, the other large:

  1. the do-while loop to avoid collisions
  2. the List container

do-while performance

The do-while has a very low impact on performance... almost negligible. This is hotly debated, but, the reality is that you would need a very, very large count before this becomes a problem. The reasoning is as follows:

Collisions happen when the random value was previously selected. For the specified range of [0 .. Int32.MaxValue), you would need a very large count before collisions actually happened. For example, count would have to be about 65,000 before there was better than a 50% chance that there was even a single collision.

In a general sense, given a Range of \$N\$, select \$M\$ numbers. If \$M < \sqrt{N}\$ then the probability of a single collision is < 50%. Since the Range is very large, the probability is small.

Obviously, if the range was small, then the probabilities would be significantly affected. But the range is fixed at Int32.MaxValue, so that's OK.

Additionally, if the count was large, then the probabilities would also be affected. How large would be very large? Well, you would be running in to very large arrays before you run in to significant problems..... I would venture you are hitting close to \$\frac{Int32.MaxValue}{2}\$ before you run in to a significant issue with performance.

List performance

This is without doubt your largest concern. You use the randomNumbers.Contains(number) call to determine whether a value was previously selected. This requires a scan of all previously-selected values to determine. As mentioned, this will almost always return false, and will thus have to scan the entire list.

As the count value increases, the length of time to perform the Contains will increase at an quadratic rate, \$O(n^2)\$ where n is count.

This performance problem will become critical much sooner than the random-collision problem.

Putting it together

The problem you have in your code is that you are trying to do too much at once, you are using a List because that is your return value, when a HashSet would be better. If you break the problem down in to stages, you will be able to solve things more elegantly.

If you add a duplicate value to a HashSet, it does not grow, and the operation performance is not dependent on the amount of data in the HashSet (it is \$O(1)\$). You can use the Count of the HashSet to manage the data uniqueness.

Once you have a clean set of unique random numbers, you can dump them in to a List, then shuffle the list using an efficient shuffle.

Combining these data structures, in the right way, leads to an overall \$O(n)\$ solution, which will scale fairly well.

Here is some code, which works in Ideone too. Note, my C# is weak, so I have tried to make the logic clear.

using System;
using System.Collections.Generic;

public class Test
{
    static Random random = new Random();

    public static List<int> GenerateRandom(int count)
    {
        // generate count random values.
        HashSet<int> candidates = new HashSet<int>();
        while (candidates.Count < count)
        {
            // May strike a duplicate.
            candidates.Add(random.Next());
        }

        // load them in to a list.
        List<int> result = new List<int>();
        result.AddRange(candidates);

        // shuffle the results:
        int i = result.Count;  
        while (i > 1)
        {  
            i--;  
            int k = random.Next(i + 1);  
            int value = result[k];  
            result[k] = result[i];  
            result[i] = value;  
        }  
        return result;
    }
    public static void Main()
    {
        List<int> vals = GenerateRandom(10);
        Console.WriteLine("Result: " + vals.Count);
        vals.ForEach(Console.WriteLine);
    }
}

The above code is my initial recommendation, and it will work well, and scale well for any reasonable number of values to return.

Second Alternate Algorithm

The problem with the above algorithm is threefold:

  1. When count is very large, the probability of collision is increased, and performance may be affected
  2. Data will need to be in both the HashSet and the List at some point, so the space usage is doubled.
  3. The shuffle at the end is needed to keep the data in a random order (HashSet does not keep the data in any specific order, and the hashing algorithm will cause the order to become biased, and skewed).

These are only performance issues when the count is very large. Note that only the collisions at large count will impact the scalability of the solution (at large count it is no longer quite \$O(n)\$, and it will be come progressively worse when count approaches Int32.MaxValue. Note that in real life this will not likely ever happen.... and memory will become a problem before performance does.

@JerryCoffin pointed to an alternate algorithm from Bob Floyd, where a trick is played to ensure that collisions never happen. This solves the problem of scalability at very large counts. It does not solve the need for both a HashSet and a List, and it does not solve the need for the shuffle.

The algorithm as presented:

initialize set S to empty
for J := N-M + 1 to N do
    T := RandInt(1, J)
    if T is not in S then
        insert T in S
    else
        insert J in S

assumes that RandInt(1, J) returns values inclusive of J.

To understand the above algorithm, you need to realize that you choose a random value from a range that is smaller than the full range, and then after each value, you extend that to include one more. In the event of a collision, you can safely insert the max because it was never possible to include it before.

The chances of a collision increase at the same rate that the number of values decreases, so the probability of any one number being in the result is not skewed, or biased.

Is this almost a final answer? No

So, using the above solution, in C#, would look like (in Ideone) (note, code is now different to Ideone):

public static List<int> GenerateRandom(int count)
{
    // generate count random values.
    HashSet<int> candidates = new HashSet<int>();
    for (Int32 top = Int32.MaxValue - count; top < Int32.MaxValue; top++)
    {
        Console.WriteLine(top);
        // May strike a duplicate.
        if (!candidates.Add(random.Next(top + 1)))
        {
            candidates.Add(top);
        }
    }

    // load them in to a list.
    List<int> result = candidates.ToList();

    // shuffle the results:
    int i = result.Count;  
    while (i > 1)
    {  
        i--;  
        int k = random.Next(i + 1);  
        int value = result[k];  
        result[k] = result[i];  
        result[i] = value;  
    }  
    return result;
}    

Note that you need to shuffle the results still, so that the HashSet issue is resolved. Also note the need to do the fancy loop-condition top > 0 because at overflow time, things get messy.

Can you avoid the shuffle?

So, this solves the need to do the collision loop, but, what about the shuffle. Can that be solved by maintaining the HashSet and the List at the same time. No! Consider this function(in Ideone too):

public static List<int> GenerateRandom(int count)
{
    List<int> result = new List<int>(count);

    // generate count random values.
    HashSet<int> candidates = new HashSet<int>();
    for (Int32 top = Int32.MaxValue - count; top < Int32.MaxValue; top++)
    {
        // May strike a duplicate.
        int value = random.Next(top + 1);
        if (candidates.Add(value))
        {
            result.Add(value);
        }
        else
        {
            result.Add(top);
            candidates.Add(top);
        }
    }

    return result;
}

The above answer is never going to allow the first value in the result to have any of the Max - Count to Max values (because there will never be a collision on the first value, and the range is not complete at that point), and this is thus a broken random generator.

Even with this collision-avoiding algorithm, you still need to shuffle the results in order to ensure a clean bias on the numbers.


TL;DR

Is This Your Final Answer? Yes!

Having played with this code a lot, it is apparent that it is useful to have a range-based input, as well as a Int32.MaxValue system. Messing with large ranges leads to potential overflows in the 32-bit integer space as well.

Working with @mjolka, the following code would be the best of both worlds:

    static Random random = new Random();

    // Note, max is exclusive here!
    public static List<int> GenerateRandom(int count, int min, int max)
    {

        //  initialize set S to empty
        //  for J := N-M + 1 to N do
        //    T := RandInt(1, J)
        //    if T is not in S then
        //      insert T in S
        //    else
        //      insert J in S
        //
        // adapted for C# which does not have an inclusive Next(..)
        // and to make it from configurable range not just 1.

        if (max <= min || count < 0 || 
                // max - min > 0 required to avoid overflow
                (count > max - min && max - min > 0))
        {
            // need to use 64-bit to support big ranges (negative min, positive max)
            throw new ArgumentOutOfRangeException("Range " + min + " to " + max + 
                    " (" + ((Int64)max - (Int64)min) + " values), or count " + count + " is illegal");
        }

        // generate count random values.
        HashSet<int> candidates = new HashSet<int>();

        // start count values before max, and end at max
        for (int top = max - count; top < max; top++)
        {
            // May strike a duplicate.
            // Need to add +1 to make inclusive generator
            // +1 is safe even for MaxVal max value because top < max
            if (!candidates.Add(random.Next(min, top + 1))) {
                // collision, add inclusive max.
                // which could not possibly have been added before.
                candidates.Add(top);
            }
        }

        // load them in to a list, to sort
        List<int> result = candidates.ToList();

        // shuffle the results because HashSet has messed
        // with the order, and the algorithm does not produce
        // random-ordered results (e.g. max-1 will never be the first value)
        for (int i = result.Count - 1; i > 0; i--)
        {  
            int k = random.Next(i + 1);  
            int tmp = result[k];  
            result[k] = result[i];  
            result[i] = tmp;  
        }  
        return result;
    }

    public static List<int> GenerateRandom(int count)
    {
        return GenerateRandom(count, 0, Int32.MaxValue);
    }
share|improve this answer
    
Why do you shuffle the results? I'm confused about this because everyone seems to include this in their answers but it isn't in the OP's question –  TopinFrassi Aug 28 at 19:27
    
@TopinFrassi: Because rolfi ordered the numbers (to check for duplicates) but they shouldn't be ordered. –  Charles Aug 28 at 20:05
    
@TopinFrassi is right he should just return candidates and it would be fine. Removing shuffling part It's only slightly better then op's answer because it uses hashset wich makes it less expensive to find a duplicate. I said this was a problem about shuffling but of course there are many implementations to fit the requirement. –  Bruno Costa Aug 28 at 22:41
3  
@BrunoCosta - The HashSet will impose a non-random (though unstructured) order on the data in the list. The OP's code would produce a random order on the result. The shuffle is required to retain the random ordered output. As for the 'slightly better' part, the HashSet will be about N/4 times faster than the List (where N is the count), so, for large N, say, 10,000 count, the HashSet will be 2500 or so times faster.... which, I guess, could be 'slight'. –  rolfl Aug 28 at 22:48
2  
I like that answer, lot of effort put in it, +1. I was worried not to see the final, filling the list on the way. But still have one objection: The randomness of the final solution is not perfect, would never allow highest value at the beginning (the shuffle helped to avoid that). I would personally use the original patched with HashSet for the test. No more changes (except codestyling). Of course I assume that it is not desired to eat the memory with a list of 2G ints -> 8GB. –  firda Sep 4 at 17:49

Yes, there definitely is.

You generate a collection of elements, mash it around and start pulling items out of it. A quick oneliner would be:

Enumerable.Range(0,100).OrderBy(x => Guid.NewGuid()).Take(20);

or alternatively

Enumerable.Range(0,100).OrderBy(x => random.Next()).Take(20);

This will give you 20 unique random values from the 0 to 100 range.

The difference with your approach is that you have a worst-case scenario of infinity: what if you are reaaaaally unlucky and end up with the same value constantly? You'll never get your required amount of random values.

My approach on the other hand will first generate 100 values and then take a subset from it which you can criticize on its memory impact. Considering you used random.Next(), which uses half the integer range, you should in fact be wary of this since it will have a huge memory impact.

It also depends on your specific situation: if you have a very large pool of values (1.000.000) and you need 2 random values then your approach will be much better. But when you need 999.999 values from that same pool, my approach will be much better still be debatable.

It will take some time to generate those last values; a lot as you can test for yourself with this:

void Main()
{
    var random = new Random();
    var times = new TimeSpan[512];
    var values = new bool[512];
    var sw = new Stopwatch();

    for(int i = 0; i < times.Length; i++) 
    {   
        sw.Restart();
        while(true) {
            int rand = random.Next();

            if(rand > 7894500 && rand < 7894512) 
            {
                int index = rand - 7894500;
                if(!values[index])
                {
                    values[index] = true;
                    break;
                }
            }
        }
        sw.Stop();
        times[i] = sw.Elapsed;
        Console.WriteLine ("Elapsed time: " + sw.Elapsed);
    }

    var orderedTime = times.OrderBy(x => x);
    for(int i = 0; i < 512; i++)
    {
        Console.WriteLine (orderedTime.ElementAt(i));
    }
}

It will keep looping randomly 512 times through your list of values and consider the element found once it finds the (randomly picked out by myself) values between 7894500 and 7894512. Afterwards this value is considered visited to correctly mimic reality (in an earlier version all 512 turns had 512 values available to them). When you execute this you'll notice it takes a lot of time to find the last values (sometimes it's fast and it takes 39 ms, other times it takes over a minute). Evidently it's fast at the start and slow at the end.

Compare that to the memory overhead of my approach which will first allocate 32 million integers, guids, padding, object overhead, etc and you're out of a big chunk of memory.

You might be able to improve it by using a more "real" shuffling algorithm which doesn't have the object and guid overhead.

Ultimately in an extreme situation where you need 32 million unique values in a randomized order out of a total population of 32 million + 1, you will either have to accept a big memory overhead or a big execution time overhead.


One last edit before this topic can be laid to rest from my part: I talked about it with @rolfl in chat and we have come to the conclusion that either of our solutions have a usage but it depends on what your situation is exactly. Summarized it would come to this:

If you have a big range of values (like 0 to int.MaxValue) then my solution will eat any memory your PC has. You're looking at two collections with each 2.1 billion integers which you then take a slice from.

In my solution you first allocate this entire population, then you sort on it (different datastructure) and then you take some of it. If this "some" is not close to 2.1 billion you will have made a huge cost of allocating data without using it.

How does this compare to @rolfl's answer? He basically allocates the data as it is needed: if he needs 32 million values then he will only allocate those 32 million (x2) and not more. If he needs 2.1 billion then he'll end up with a memory footprint like I have but that's an uncommon worst case scenario while for me it is standard behaviour.

The main disadvantage of his approach is that when the amount of values you want reaches the total population, it will become increasingly harder to get those last values because there will be many collisions. Yet again, this will only be a problem when the population is actually really big.

So when should you use my solution? Like most things, there is a tradeoff between readability and performance. If you have a relatively small population and a large dataset then the readability weighs up against the performance impact, in my opinion. And when the population is relatively small and the amount of values we want is near that, my solution will have a memory impact similar to that of the other approach but it will also avoid many collisions.

Take your pick depending on what your situation is.

share|improve this answer
2  
-1 because this code is not compatible with the OP's requirements as is, and would likely not complete successfully with a large range (MIN to MAX value for Int). –  rolfl Aug 28 at 14:30
2  
If you need 999,999 values from 1,000,000 then your code will require.... about 16MB just to store the GUID's (assuming it is stored in a complact 16-byte value, not as a string, or something) , plus another 4MB for the int values, plus object overheads, and then some more too, i am sure. –  rolfl Aug 28 at 14:35
11  
Additionally, GUID's are not specified to be random, and ordering by a GUID will not produce the results you expect –  rolfl Aug 28 at 14:39
2  
just replace it by a random and you wouldn't complain about it anymore @rofl Random r = new Random(); Enumerable.Range(0,100).OrderBy(x => r.Next()).Take(20).Dump(); –  Bruno Costa Aug 28 at 15:11
3  
A sorting function is not a shuffling function. Why generate O(N) new memory for the key and take O(N log N) time to sort it, when you can use the Fischer-Yates shuffle which takes O(1) memory and O(N) time? –  Andrew Piliser Aug 30 at 12:53

Instead of using a List<int>, you should use an HashSet<int>. The HashSet<> prohibites multiple identical values. And the Add method returns a bool that indicates if the element was added to the list, this way you could change this code :

public static List<int> GetRandomNumbers(int count)
{
    List<int> randomNumbers = new List<int>(); 

    for (int i=0; i<count; i++) 
    {    
        int number;

        do number = random.Next();
        while (randomNumbers.Contains(number));

        randomNumbers.Add(number);
    }

    return randomNumbers;
}

to this :

public static IEnumerable<int> GetRandomNumbers(int count)
{
    HashSet<int> randomNumbers = new HashSet<int>();

    for (int i = 0; i < count; i++) 
        while (!randomNumbers.Add(random.Next()));

    return randomNumbers;
}

Note that I changed the return value from List<int> to IEnumerable<int>, if you don't plan to add/remove values from your list, you should return IEnumerable<int>, if you plan to do it, return ICollection<int>. You shouldn't return a List<int> because it is an implementation detail and that the List<> isn't made to be extensible.

share|improve this answer
    
The problem about using a Set is that it's not ordered. There's no way to make it put the integers in a random order. –  Simon André Forsberg Aug 28 at 14:30
1  
@SimonAndréForsberg The OP didn't specify he wanted to do so, unless there's something I'm missing –  TopinFrassi Aug 28 at 14:34
1  
In fact, you are correct. I totally misread the problem. –  Simon André Forsberg Aug 28 at 14:45
    
Happens to everyone! –  TopinFrassi Aug 28 at 14:45
    
you shouldn't call ToList there. Asside of that it is a great solution –  Bruno Costa Aug 28 at 23:39

Expanding on my comment. This is called a linear congruential generator. I used common parameters, which come from what I think is called the Minimal Standard. Other parameters can be chosen, but that's a tricky task. The sequence starts at the seed, reaches all other numbers between 0 and M-1, and then restarts once it reaches the seed again. It's pseudo-random. 507111939 always follows 285719. Since the sequence reaches all M numbers, there will be no duplicates in any M successive outputs of the sequence.

Code:

class RandomSequence {

  int actual;
  static final int M = (1<<31) -1;

  public RandomSequence(int seed) {
    this.actual = seed
  }

  public int next() {
    return this.actual = (16807 * this.actual) % RandomSequence.M
  }

}

Usage :

//...
List<int> awesomeList = new List<int>();
RandomSequence sq = new RandomSequence( RandomUtil.getRandomPositiveIntSmallerThanM() );
for(int i = 0; i < n; i++) {
  awesomeList.add(sq.next());
}
share|improve this answer
3  
This is a nice solution. You should note that a fair amount of this works because of a number of convenient coincidences in computational theory, like M is \$2^{31} - 1\$ which is also Integer.Max_value, and it also happens to be a prime number. Being prime is significant. 16807 is also prime. –  rolfl Aug 30 at 12:49

The algorithm looks fine to me. It shows no clear flaws, and will work fine in common use cases.
For extreme cases of selecting most of the numbers in a very large interval, it will be very inefficient. But unless that is an expected use case, I would not bother changing the code to more complicated approaches.

But I suggest you always use explicit braces around blocks even when they have a single statement:

do
{
    bar();
}
while (foo);

I would also rename the method to GetNRandomNumbers, to make the method's name match its purpose better.

share|improve this answer
2  
+1. I'm not usually a stickler for braces around blocks, but I think in a do ... while loop they're especially important. I initially misread the code because of the lack of braces. –  Jules Aug 30 at 2:37
    
Style wan't the question, was it? –  Florian F Sep 4 at 16:43
1  
@FlorianF No, it was not. But the first sentence in the answer says that the algorithm looks fine to me, does it not? And then I made some sugestions to improve bug resilience (using brackets) and clarity (renaming). Could you try to you be clearer in what you mean? –  ANeves Sep 4 at 17:43
5  
@FlorianF Style is always a valid target for a code review. –  David Harkness Sep 4 at 18:35
7  
@FlorianF this is Code Review, not Stack Overflow. Reviewers are always free to comment on any aspect of the code. Always. –  Mat's Mug Sep 4 at 23:44

Another solution is to use a Format Preserving Encryption cipher (such as AES using the FFX mode), configured to map from 32 bit integers to 32 bit integers.

Seed it randomly, then simply encrypt the first 'count' integers.

These encrypted numbers will be as random as the seed, and won't repeat.

share|improve this answer
    
Interesting idea, and probably much faster than OP's and rolfl's code, as it would be O(n) not O(n^2) or O(n ln n) as those solutions are. Jeroen Vannevel's solution is also O(n) and would probably be faster still, but cannot plausibly be used if the required range of the random numbers is too large. This solution likely has the lowest memory requirement of all, as the numbers can be produced on-demand rather than calculated in advance. –  Jules Aug 30 at 2:41

I'm updating my answer in order to make an analysis on BobFloyd's algorithm and sum up all flaws that I could spot on it. Some of them were on my previous answer, they are also mentioned on some users comments like @rolfl and @firda. Please follow through the whole answer because you will have a surprise at the end.

Let me define some terms that I'll be using in my answer. Consider the method definition:

static IEnumerable<int> NonRepeatingRandomSequence(int min, int max, int count, int? seed = null)
  • range length = max - min + 1
  • taken elements = count

First issue: The last range length - taken elements elements can not ever be in index 0 of the result.

Second issue: The results becomes closer to a linear sequence as taken elements gets closer to range length. This is easier to see when they are the same, but the result is not random at all when they are close.

Third issue: There is also a third issue but I will just mention it at end of my answer.

I implemented three algorithms for returning non repetitive Numbers:

A pure shuffling algorithm, A pure Bob Floyd algorithm and a Bob Floyd algorithm with shuffling. Those will appear later as I compare and test them.

I also implemented a test to check the randomness of the outputted list by any algorithm. Although it has some constraints, it will suffice for the sake of the answer completeness/correctness. For much wrong it can be this will be my definition of being random. In here I'm basically count the times that every combination occurs and see if the average is in an acceptable range.

public void TestRandomness(Func<List<int>> getRandomList, int rangeLength, int count)
{
    long combinations = (long)(rangeLength.Factorial(rangeLength - count + 1));
    long iterations = combinations * 100;
    var partitioner = Partitioner.Create(0, iterations, iterations / 4);
    ConcurrentDictionary<long, int> ocurrences = new ConcurrentDictionary<long, int>(Environment.ProcessorCount, (int)combinations);

    Parallel.ForEach(partitioner, new ParallelOptions() {MaxDegreeOfParallelism = Environment.ProcessorCount},
        range =>
        {
            //hopefully having a private dictionary will help concurrency
            Dictionary<long, int> privateOcurrences = new Dictionary<long, int>();
            for (long i = range.Item1; i < range.Item2; ++i)
            {
                var list = getRandomList();
                long acc = 0;
                //this will only work when numbers are between 0 and 88
                foreach (var value in list)
                {
                    acc = (value + 11) + acc*100;
                }
                privateOcurrences.AddOrUpdate(acc, 1, v => v + 1);
            }
            foreach (var privateOcurrence in privateOcurrences)
            {
                ocurrences.AddOrUpdate(privateOcurrence.Key, 
                    privateOcurrence.Value,
                    (k, v) => v + privateOcurrence.Value);
            }
        });

    double averageOcurrences = iterations / combinations;
    double currentAverage = ocurrences.Values.Average();
    Debug.WriteLine("The average ocurrences of this implementation is {0} comparing to {1} in the 'perfect' scenario", currentAverage, averageOcurrences);
    Assert.Less(currentAverage, averageOcurrences * 1.05);
    Assert.Greater(currentAverage, averageOcurrences * 0.95);
}

So let's start with testing the randomness of our shuffling algorithm, this is my first algorithm:

[Test]
public void TestShuffleRandomness()
{
    TestRandomness(() => Enumerable.Range(0, 16).ToList().Shuffle().Take(4).ToList(), 16, 4);    
}

Pass, pass, pass. This algorithm respects my test definition of randomness. This is very close to what @Jeroen Vannevel pointed, except for the part this do not require a random nor does it run in O(n log n) time (I need to refer to @Andrew Piliser because he was the only one to comment about this).

As we know this algorithm will take memory equivalent to O(range length) and it is his major drawback. However it does not generate collisions and it guarantees randomness.

It's now time to prove First and Second issues with Bob Floyd Algorithm:

public static IEnumerable<int> BobFloydNonRepeatingSequence(int min, int max, int count, int? seed = null)
{
    Random random;
    if (seed != null)
    {
        random = new Random(seed.Value);
    }
    else
    {
        random = new Random();
    }
    long length = max - min + 1;
    INonRepeatingList values = NonRepeatingListFactory.GetNonRepeatingList(min, max, count);
    for (int i = (int)(length - count); i < length; ++i)
    {
        if (!values.Add(random.Next(min, i+min+1)))
        {
            values.Add(i+min);
        }
    }
    return values;
}

[Test]
public void TestLastCountElementsAreNotInIndex0()
{
    for (int i = 0; i < 1000000; ++i)
    {
        var list = Sequence.BobFloydNonRepeatingSequence(0, 15, 4).ToList();
        Assert.IsFalse(new[] { 12, 13, 14, 15 }.Contains(list[0]));
        Assert.AreEqual(4, list.Count);
    }
}

[Test]
public void TestBobFloydBecomesLinear()
{
    var list = Sequence.BobFloydNonRepeatingSequence(0, 15, 16).ToList();
    for (int i = 0; i < list.Count; ++i)
    {
        Assert.AreEqual(i, list[i]);
    }
}

Great, now we proven that Bob Floyd algorithm by it's own does not solve this problem and of course it wouldn't pass in my randomness test.

[Test]
public void TestBobFloydRandomness()
{
    TestRandomness(() => Sequence.BobFloydNonRepeatingSequence(0, 15, 4).ToList(), 16, 4);
}

Our only option left is to shuffle the results and hope for the best.

public static IEnumerable<int> NonRepeatingRandomSequence(int min, int max, int count, int? seed = null)
{
    Random random;
    if (seed != null)
    {
        random = new Random(seed.Value);
    }
    else
    {
        random = new Random();
    }
    long length = max - min + 1;
    INonRepeatingList values = NonRepeatingListFactory.GetNonRepeatingList(min, max, count);
    for (int i = (int)(length - count); i < length; ++i)
    {
        if (!values.Add(random.Next(min, i+min+1)))
        {
            values.Add(i+min);
        }
    }
    values.Shuffle();
    return values;
}

Let's see what my randomness test says about this:

[Test]
public void TestBobFloydWithShuffleRandomness()
{
    TestRandomness(() => Sequence.NonRepeatingRandomSequence(0, 15, 4).ToList(), 16, 4);
}

I hope you didn't get your hopes too high. My randomness test fails this is the third and last issue with Bob Floyd at all because it won't be random. Or at least it does not respect the definition of random that I provided.

This bit will be just discussing my implementation of Bob Floyd algorithm vs rolfl one

So let's say my definition of random is a bit strict or that Bob Floyd shuffled algorithm is random enough for your purposes. I don't really know what is lacking in the implementation so that the results would be more random, so it just remains about efficiency.

As you saw in my implementation I am getting a INonRepeatingList from the method NonRepeatingListFactory.GetNonRepeatingList.

public class NonRepeatingListFactory
{
    public static INonRepeatingList GetNonRepeatingList(int min, int max, int count)
    {
        long length = max - min + 1;
        if (length / 8 > count * 2 * sizeof(int))
        {
            //if the amount of bytes occupied by the array is greater then the dictionary
            return new RandomIndexNonRepeatingList();
        }
        return new NonRepeatingList(min, max);
    }
}

This Method decides which list to use based on memory occupied. If you use a HashSet always like @rolfl suggests you will be occupying to much memory when taken elements is big and range length is also big. In this situation you can just map the value to a bit. How much difference it may make? It's just about 1KB memory for every 8KB range length. In the other hand if we are taking few elements from a wide range we should be using an HashSet.

public interface INonRepeatingList : IEnumerable<int>
{
    bool Add(int value);
}

internal class NonRepeatingListWithArray : List<int>, INonRepeatingList
{
    private readonly BitArray inList;
    private readonly int min;
    private readonly int max;

    public NonRepeatingListWithArray(int min, int max)
    {
        this.inList = new BitArray(max-min+1);
        this.min = min;
        this.max = max;
    }

    bool INonRepeatingList.Add(int value)
    {
        if (!this.inList[value - this.min])
        {
            this.Add(value);
            this.inList[value - this.min] = true;
            return true;
        }
        return false;
    }
}

internal class NonRepeatingListWithSet : List<int>, INonRepeatingList
{
    private readonly HashSet<int> mapValue = new HashSet<int>();
    private int currentIndex = 0;

    bool INonRepeatingList.Add(int value)
    {
        if (mapValue.Add(value))
        {
            base.Add(value);
            return true;
        }
        return false;
    }
}

Full code on pastebin

share|improve this answer
    
after a quick overview I noticed that I wasn't using a Random thread safely but despite of this my tests results didn't change. –  Bruno Costa Sep 6 at 0:39
    
There are errors in your translation of Bob Floyd's algorithm; try Sequence.BobFloydNonRepeatingSequence(8, 14, 3, 7) -- it throws an ArgumentOutOfRangeException. –  mjolka Sep 7 at 8:43
    
@mjolka thanks again. I updated my answer accordingly. –  Bruno Costa Sep 7 at 13:19
    
There's still a mistake in the Bob Floyd algorithm; values.Add(i+min) should be values.Add(i+min-1). –  mjolka Sep 8 at 0:21
    
@mjolka No it shouldn't. –  Bruno Costa Sep 8 at 6:12

Though the solution byr @Jeroen Vannevel is quite simple and works for most intents and purposes, you will see especially poor performance if you just want a few numbers out of a very large range.

In that case I recommend the following algorithm:

  1. Pick one number out of the range
  2. Pick one number out of the remaining range
  3. and so on ...

The implementation could look like so:

  1. Choose a number from 0 to N
  2. Choose a number from 0 to N-1
  3. And so on
  4. Determine which number each of your drawings represents

Example for 0 to 10

  1. draw 4
  2. draw 7
  3. ...
  4. Results in: the 4 represents 4, the 7 represents 8
share|improve this answer
    
Could you add a code example of your algo? –  TopinFrassi Aug 28 at 14:22
    
This will work, but will provide some additional overhead after you've randomized 5, 6 for example and you get an 7 as the next number. I assume you intend that 7 to be modified into a 9 then? (because 5 and 6 is already gone). –  Simon André Forsberg Aug 28 at 14:34
    
@SimonAndréForsberg Exactly, you would have to try when the overhead is worth the extra effort but when increasing the range there should be a turning point where this becomes more efficient. –  Dennis Jaheruddin Aug 28 at 14:41
1  
I see the implication here, and that I mistook the algorithm you suggest. You are correct, there will be no skewness, but your answer leaves a very big blank over how to manage the range, especially given that the range is the whole valid int 32-bit space. You will still need to iterate over all the previously selected values to make it work. –  rolfl Aug 28 at 14:46
1  
This needs to be explained better. (The part that the second number is increased by 1 if it is bigger than the first, and the 3rd by 2 if bigger than both or 1 if bigger than one, etc.) –  ANeves Aug 28 at 16:46

From the looks of it, what you want is called a (pseudo)random permutation of all int values. Note that you don't necessarily have to store these values in an array and shuffle them, consuming memory; you can actually generate them on demand via a "perfect" hash function of the bits in the "count" variable.

Note that pseudo-random also means deterministic, so to get different values on different runs, you have to make sure to "seed" your sequence with a different value each time.

share|improve this answer

You have two parameters: the number N of integers you want, and their maximum size M >= N. If N is close to M, e.g., you want 500 numbers in the range 1..1000, then your best bet is to (partially) shuffle the numbers 1..M. For example, you can run the first N steps of a Fisher-Yates shuffle on 1..M and get the numbers you need.

Otherwise, if M is a lot bigger than N, you would be better off generating all your random numbers at once (rather than checking if they're in the list one-by-one), sorting, removing duplicates, adding new elements as needed for replacements, and then re-shuffling.

You may wish to generate more than N numbers to handle the expected number of duplications. The expected number of duplicates is about N(N-1)/2M so you might generate, say, N + 1.1N(N-1)/2M numbers in your initial list.

Sorting and removing duplicates is standard.

If you're not over-generating, or if you did but it wasn't enough, you can generate new elements as you originally suggested: generate a new number, test if it's on the list, and add it if so.

For re-shffling you can either use a standard shuffle (like Fisher-Yates, mentioned above) or you can store the original order with each element and then order by that. If you do and you over-generated originally, just ignore any extra elements on the end.

If performance is important, you can code both methods (and maybe several variants of the second, as described) and test to find the cutoff between the methods. If it isn't then the second method will work in all cases -- though if you don't need it the first is easier to program.

share|improve this answer
    
The OP only has one parameter, N. What you call the second parameter M is actually hard-coded in the code as random.Next() which implies an M of Integer.MAX_VALUE (2^31 - 1). –  rolfl Aug 30 at 12:30
    
@rolfl: Correct. I wanted to spell out the dependence on M explicitly. –  Charles Aug 31 at 19:22

I'll give a short answer.

Since your random numbers are 32-bit integers, the chances of a collision are very low. In this case, the do ... while loop will loop only occasionally and won't cause any performance problem.

The problem is how you check for a collision. Checking whether a number belongs to a list requires to read the list sequentially That is slow. You should better use a HashMap. Insert each generated number in the HashMap, and check new numbers against the HashMap.

Since you want to return the numbers as a List, you will have to also collect the numbers in a List. You can either build the List as the numbers are generated, or build the list later, from the HashMap. But the second solutions compromises the randomness, and you will have to shuffle the numbers again. And to actually save memory you have to empty the HashMap as you build the List. Emptying the HashMap one element at a time adds overhead.

A complete different solution that minimizes memory use would be to generate N random numbers in the range 0 to Int21.MaxValue-N+1, sort the list, add i the ith element, and shuffle the list again. It minimizes memory use but is O(N log N) run time.

The List + HashMap solution is almost O(N) run time but requires at least twice that much memory.

share|improve this answer

If there are 1-4 possible numbers, and you have generated 1 number already, that means there are (4 - 1) 3 possible numbers left. Make a random number between 3, for every generate number it is greater than or equal, increase the created number by 1.

lets say the number is 2, and you want to generate another:

Generated numbers: [1,2,3] Possible number: [1,3,4]

Solution:

public static int[] GetRandomNumbers(int count, int minValue, int maxValue)
{
    int[] randomNumbers = new int[count]; 

    for (int i=0; i < count; ++i) 
    {      
        //Given (min - max) is the range, there can only be (range - i) unique number left
        int number = random.Next(minValue, maxValue - i);

        //if the number is greater than or equal to, then increase the number
        for (int j=0; j < i; ++j)
            if(number >= randomNumbers[j])
                ++number; 

        randomNumbers.Add(number);
    }

    return randomNumbers;
}
share|improve this answer
1  
+1 for providing what looks to be a working solution that avoids the possible duplicate-value check. Note your solution scales badly for large values of count though. \$O(n^2)\$ time complexity –  rolfl Aug 30 at 12:38
1  
This doesn't compile (there's no Add method for array), and it produces duplicate values. After getting it to compile, on my machine, GetRandomNumbers(10, 0, 20, new Random(7)) produces 7, 17, 12, 0, 6, 13, 1, 18, 15, 13. –  mjolka Sep 1 at 6:45

First of all, there is one unspecified variable random and my best bet would be to assume it is System.Random and the Next method returns

A 32-bit signed integer greater than or equal to zero and less than MaxValue.

I ask the author to make this clear in the question. With this assumption, we have algorithm that works for count < int.MaxValue, but gets very slow for count close to that value, but that would mean eating nearly 8GB memory (2G*4B). We can try to make it faster for count greater than some threshold, e.g. 20 (subject to benchmarking), throw exception for some ridiculous count and rewrite it like this:

public static List<int> GetRandomNumbers(int count) {
    if(count > int.MaxValue/8)
        throw new MyException("count too big");

    List<int> randomNumbers = new List<int>(count); 
    if(count < 20) for (int i=0; i<count; i++) {
        int number; do number = random.Next(); // I will address the 'uglyness' later
        while (randomNumbers.Contains(number));
        randomNumbers.Add(number);
    } else {
        HashSet<int> included = new HashSet<int>();
        for(int i=0; i<count; i++) {
            int number; do number = random.Next();
            while (!included.Add(number));
            randomNumbers.Add(number);
        }
    }
    return randomNumbers;
}

The do..while may seem ugly, but is separated by two empty lines (in original code), thus makes it sufficient but still subject to further rethinking regarding to who may be maintaining the code. I will not address this furteher, because it depends on how many people may maintain the code and programmer's preferences (I will not address code-style while I see one). I am not that strict in this and for me, two empty lines (one before and one after) is enought to signal it needs more thinking when encountered and I will never touch a code that works and is optimal. Comments can help to describe the intent, code is to be reviewed when there is something wrong (does not work or is slow). The following may look better by using {}, more end-of-lines and few comments:

public static List<int> GetRandomNumbers(int count) {
//  eating too much memory is not desired
    if(count > int.MaxValue/8)
        throw new MyException("count too big");

    List<int> randomNumbers = new List<int>(count);
    if(count < 20) {
    //  list is fast enough for small count
        for (int i=0; i<count; i++) {
            int number;
            do {
                number = random.Next();
            } while (randomNumbers.Contains(number));
            randomNumbers.Add(number);
        }
    } else {
    //  but HashSet is faster for longer sequence
        HashSet<int> included = new HashSet<int>();
        for(int i=0; i<count; i++) {
            int number;
            do {
                number = random.Next();
            } while (!included.Add(number));
            randomNumbers.Add(number);
        }
    }
    return randomNumbers;
}
share|improve this answer

The idei is to create segments in the defined range and pick one value from them randomly with taking the segments also randomly. No overlapping will happen and also works with negative values.

    public static IEnumerable<int> GetRandomNumbers(int count, int minValue, int maxValue)
    {
        if (count < 1)
        {
            throw new ArgumentException("Count must be greater then 0", "count");
        }

        if (count > Math.Abs(maxValue - minValue))
        {
            throw new ArgumentException("MaxValue must be greater than count", "maxValue");
        }

        var segmentSize = (maxValue - minValue) / count;
        var random = new Random();
        var steps = Enumerable.Range(0, count).ToList();

        while (steps.Count != 0)
        {
            var currentIndex = random.Next(0, steps.Count);
            var index = steps[currentIndex];
            steps.RemoveAt(currentIndex);

            yield return random.Next((index * segmentSize) + minValue, ((index + 1) * segmentSize) + minValue);
        }
    }

    public static IEnumerable<int> GetRandomNumbers(int count)
    {
        return GetRandomNumbers(count, 0, int.MaxValue);
    }
share|improve this answer
    
This doesn't work. GetRandomNumbers(3, 0, 4) always returns 0, 1, 2. –  mjolka Sep 7 at 8:00
    
True but depending on the business needs it can solve the problem in a very simple way. And the problem can be solved by expending randomly the segments with (maxValue - minValue) % count. –  Peter Kiss Sep 7 at 8:42
3  
But if I want three numbers chosen at random from the range [0, 4) i.e. GetRandomNumbers(3, 0, 4), I would expect a 3 to appear with equal probability as 0, 1, and, 2. –  mjolka Sep 7 at 9:12

protected by 200_success Sep 4 at 21:49

Thank you for your interest in this question. Because it has attracted low-quality answers, posting an answer now requires 10 reputation on this site.

Would you like to answer one of these unanswered questions instead?

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