How to ensure that randomly generated numbers are not being repeated? [duplicate]

Question

Possible Duplicates:
Unique (non-repeating) random numbers in O(1)?
How do you efficiently generate a list of K non-repeating integers between 0 and an upper bound N

I want to generate random number in a certain diapason, and I must be sure, that each new number is not a duplicate of formers. One solution is to store formerly generated numbers in a container and each new number checks aginst the container. If there is such number in the container, then we generate agin, else we use and add it to the container. But with each new number this operation is becoming slower and slower. Is there any better approach, or any rand function that can work faster and ensure uniqueness of the generation?

EDIT: Yes, there is a limit (for example from 0 to 1.000.000.000). But I want to generate 100.000 unique numbers! (Would be great if the solution will be by using Qt features.)

Answer 1

Is there a range for the random numbers? If you have a limit for random numbers and you keep generating unique random numbers, then you'll end up with a list of all numbers from x..y in random order, where x-y is the valid range of your random numbers. If this is the case, you might improve speed greatly by simply generating the list of all numbers x..y and shuffling it, instead of generating the numbers.

Answer 2

I think there are 3 possible approaches, depending on range-size, and performance pattern needed you can use another algorithm.

1. Create a random number, see if it is in (a sorted) list. If not add and return, else try another.
   • Your list will grow and consume memory with every number you need. If every number is 32 bit, it will grow with at least 32 bits every time.
   • Every new random number increases the hit-ratio and this will make it slower.
   • O(n^2) - I think
2. Create an bit-array for every number in the range. Mark with 1/True if already returned.
   • Every number now only takes 1 bit, this can still be a problem if the range is big, but every number now only allocates 1 bit.
   • Every new random number increases the hit-ratio and this will make it slower.
   • O(n*2)
3. Pre-populate a list with all the numbers, shuffle it, and return the Nth number.
   • The list will not grow, returning numbers will not get slower,
   • but generating the list might take a long time, and a lot of memory.
   • O(1)

Depending on needed speed, you could store all lists in a database. There's no need for them to be in memory except speed.