smart way to generate unique random number

Question

i want to generate a sequence of unique random numbers in the range of 00000001 to 99999999.

So the first one might be 00001010, the second 40002928 etc.

The easy way is to generate a random number and store it in the database, and every next time do it again and check in the database if the number already exists and if so, generate a new one, check it again, etc. But that doesn't look right, i could be regenerating a number maybe 100 times if the number of generated items gets large.

Is there a smarter way?

EDIT as allways i forgot to say WHY i wanted this, and it will probably make things clearer and maybe get an alternative, and it is: we want to generate an ordernumber for a booking, so we could just use 000001, 000002 etc. But we don't want to give the competitors a clue of how much orders are created (because it's not a high volume market, and we don't want them to know if we are on order 30 after 2 months or at order 100. So we want to have an order number which is random (yet unique)

Answer 1

Use Pseudo-random Number Generators.

For example - Linear Congruential Random Number Generator

(if increment and n are coprime, then code will generate all numbers from 0 to n-1):

    int seed = 1, increment = 3;
    int n = 10;

    int x = seed;
    for(int i = 0; i < n; i++)
    {
        x = (x + increment) % n;
        Console.WriteLine(x);
    }

Output: 4 7 0 3 6 9 2 5 8 1

Basic Random Number Generators

Mersenne Twister

Answer 2

You could try giving writing usernames by using a starting number and an incremental number. You start at a number (say, 12000), then, for each account created, the number goes up by the incremental value.

id = startValue + (totalNumberOfAccounts * inctrementalNumber)

If incrementalNumber is a prime value, you should be able to loop around the max account value and not hit another value. This creates the illusion of a random id, but should also have very little conflicts. In the case of a conflicts, you could add a number to increase when there's a conflict, so the above code becomes. We want to handle this case, since, if we encounter one account value that is identical, when we increment, we will bump into another conflict when we increment again.

id = startValue + (totalNumberOfAccounts * inctrementalNumber) + totalConflicts

Answer 3

Running a linear congruential generator once to generate each number is apt to produce rather feeble results. Running it through a number of iterations which is relatively prime to your base (100,000,000 in this case) will improve it considerably. If before reporting each output from the generator, you run it through one or more additional permutation functions, the final output will still be a duplicate-free permutation of as many numbers as you want (up to 100,000,000) but if the proper functions are chosen the result can be cryptographically strong.

Answer 4

You could try shuffling the set of possible values then using them sequentially.

Answer 5

I like Lazarus's solution, but if you want to avoid effectively pre-allocating the space for every possible number, just store the used numbers in the table, but build an "unused numbers" list in memory by adding all possible numbers to a collection then deleting every one that's present in the database. Then select one of the remaining numbers and use that, adding it to the list in the database, obviously.

But, like I say, I like Lazaru's solution - I think that's your best bet for most scenarios.

Answer 6

System.Random rnd = new System.Random();
IEnumerable<int> numbers = Enumerable.Range(0, 99999999).OrderBy(r => rnd.Next());

This gives a randomly shuffled collection of ints in your range. You can then iterate through the collection in order.

The nice part about this is that you're not actually creating the entire collection in memory.

See comments below - this will generate the entire collection in memory when you iterate to the first element.