# Solved: unique random numbers. Implementation in C++



## burnthepc (Aug 12, 2007)

I need a really fast way to get N unique random numbers. (N will be fairly small - something like 50 avg 100 max)
Obviously something like rand() N times is not going to guarantee they are unique.(I know rand() from cstdlib isn't that fast - I'll replace it at some point.)

I was thinking something like this (psudocode version)

```
vector<int> numbers
for ( 1-N ) numbers.push_back(rand())

do
if(numbers.size() != N) add more numbers

?? sort(numbers) and if numbers[i] == numbers[i-1] delete one of the pair?
?? binary search for each element and delete duplicates?
while (numbers.size() != N)
```
What do you guys think? I'm sure I'm not the first person ever to need a set of unique random numbers so I thought I'd see what the general opinion is.

Issues I'm considering are:

List or vector? May need some deletes from inside (list?) but binary search might be fast enough to make up for the occasional duplicates in the random numbers.

Should I use a Set<int>? I've never come across them but the unique property has just struck me as what I might need.

Any other STL algorithms that can help out?


----------



## pvc_ (Feb 18, 2008)

I know the fastest sorting algorithm that you may use for this would have a O complexity (quick sort for instance). And you'd have to run it everytime a new number is added to your vector or list, so it'd be a O(n ^ 2) overall complexity. The good thing about a list is that it has a built-in sorting algorithm. 

If I had to do something like this, I'd just generate the random number, then I'll run a for loop to see if that number is already in the vector, or list. If it wasn't, then the number would be added to the list. This method would also have a O(n ^ 2) complexity


----------



## burnthepc (Aug 12, 2007)

Thanks for the input pvc_ . I like your second idea. I think I'll use it. It's simple enough and as you say it'll run at least as fast as a the list version. Plus it could have advantages if I need to start passing these containers round as I've used vectors in a lot of other places.


----------



## JimmySeal (Sep 25, 2007)

I think using a hash table would be somewhat faster than a list. 50-100 items seems about big enough to merit the extra overhead.


----------

