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

How about creating a set all of possible numbers and simply randomising the order? You could then just pick the next number from the tail.

Each number appears only once in the set, and when you want a new one it has already been generated, so the overhead is tiny at the point at which you want one. You could do this in memory or the database of your choice. You'll just need a sensible locking strategy for pulling the next available number.

Answer 2

You could just place your numbers in a set. If the size of the set after generation of your N numbers is too small, generate some more.

Do some trial runs. How many numbers do you have to generate on average? Try to find out an optimal solution to the tradeoff "generate too many numbers" / "check too often for duplicates". This optimal is a number M, so that after generating M numbers, your set will likely hold N unique numbers.

Oh, and M can also be calculated: If you need an extra number (your set contains N-1), then the chance of a random number already being in the set is (N-1)/R, with R being the range. I'm going crosseyed here, so you'll have to figure this out yourself (but this kinda stuff is what makes programming fun, no?).

Answer 3

function getShuffledNumbers(count) {
 var shuffledNumbers = new Array();
 var choices = new Array();
 for (var i = 0; i<count; i++) {
  // choose a number between 1 and amount of numbers remaining
  choices[i] = selectedNumber = Math.ceil(Math.random()*(99999999 - i));
  // Now to figure out the number based on this selection, work backwards until
  // you figure out which choice this number WOULD have been on the first step
  for (var j = 0; j < i; j++) {
   if (choices[i - 1 - j] >= selectedNumber) {
    // This basically says "it was choice number (selectedNumber) on the last step,
    // but if it's greater than or equal to this, it must have been choice number
    // (selectedNumber + 1) on THIS step."
    selectedNumber++;
   }
  }
  shuffledNumbers[i] = selectedNumber;
 }
 return shuffledNumbers;
}

This is as fast a way I could think of and only uses memory as it needs, however if you run it all the way through it will use double as much memory because it has two arrays, choices and shuffledNumbers.

Answer 4

1. create and store ind db two shuffled versions(SHUFFLE_1 and SHUFFLE_2) of the interval [0..N), where N=10'000;

2. whenever a new order is created, you assign its id like this:

ORDER_FAKE_INDEX = N*SHUFFLE_1[ORDER_REAL_INDEX / N] + SHUFFLE_2[ORDER_REAL_INDEX % N]

Answer 5

You could put a unique constraint on the column that contains the random number, then handle any constraint voilations by regenerating the number. I think this normally indexes the column as well so this would be faster.

You've tagged the question with C#, so I'm guessing you're using C# to generate the random number. Maybe think about getting the database to generate the random number in a stored proc, and return it.

Answer 6

the stupid way: build a table to record, store all the numble first, and them ,every time the numble used, and flag it as "used"