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

You could build a table with all the possible numbers in it, give the record a 'used' field.

1. Select all records that have not been 'used'
2. Pick a random number (r) between 1 and record count
3. Take record number r
4. Get your 'random value' from the record
5. Set the 'used' flag and update the db.

That should be more efficient than picking random numbers, querying the database and repeat until not found as that's just begging for an eternity for the last few values.

Answer 2

You can use either an Linear Congruential Generator (LCG) or Linear Feedback Shift Register (LFSR). Google or wikipedia for more info.

Both can, with the right parameters, operate on a 'full-cycle' (or 'full period') basis so that they will generate a 'psuedo-random number' only once in a single period, and generate all numbers within the range. Both are 'weak' generators, so no good for cyptography, but perhaps 'good enough' for apparent randomness. You may have to constrain the period to work within your 'decimal' maximum as having 'binary' periods is necessary.

Update: I should add that it is not necessary to pre-calculate or pre-store previous values in any way, you only need to keep the previous seed-value (single int) and calculate 'on-demand' the next number in the sequence. Of course you can save a chain of pre-calculated numbers to your DB if desired, but it isn't necessary.

Answer 3

By fallowing line we can get e.g. 6 non repetitive random numbers for range e.g. 1 to 100.

var randomNumbers = Enumerable.Range(1, 100)
    .OrderBy(n => Guid.NewGuid())
    .Take(6)
    .OrderBy(n => n);

Answer 4

In case you happen to have access to a library and you want to dig into and understand the issue well, take a look at

The Art of Computer Programming, Volume 2: Seminumerical Algorithms

by Donald E. Knuth. Chapter 3 is all about random numbers.

Answer 5

I've had to do something like this before (create a "random looking" number for part of a URL). What I did was create a list of keys randomly generated. Each time it needed a new number it simply randomly selected a number from keys.Count and XOR the key and the given sequence number, then outputted XORed value (in base 62) prefixed with the keys index (in base 62). I also check the output to ensure it does not contain any naught words. If it does simply take the next key and have a second go. Decrypting the number is equally simple (the first digit is the index to the key to use, a simple XOR and you are done).

I like andora's answer if you are generating new numbers and might have used it had I known. However if I was to do this again I would have simply used UUIDs. Most (if not every) platform has a method for generating them and the length is just not an issue for URLs.

Answer 6

I also came with same kind of problem but in C#. I finally solved it. Hope it works for you also.

Suppose I need random number between 0 and some MaxValue and having a Random type object say random.

int n=0;
while(n<MaxValue)
{
   int i=0;
   i=random.Next(n,MaxValue);
   n++;
   Write.Console(i.ToString());
}