Get X unique numbers from a set

Question

What is the most elegant way to grab unique random numbers I ponder?

At the moment I need random unique numbers, I check to see if it's not unique by using a while loop to see if I've used the random number before.

So It looks like:

int n = getRandomNumber % [Array Size];

for each ( Previously used n in list)
    Check if I've used n before, if I have...try again.

There are many ways to solve this linear O(n/2) problem, I just wonder if there is a elegant way to solve it. Trying to think back to MATH115 Discrete mathematics and remember if the old lecturer covered anything to do with a seemingly trivial problem.

I can't think at the moment, so maybe once I have some caffeine my brain will suss it with the heightened IQ induced from the Coffee.

Answer 1

If you want k random integers drawn without replacement (to get unique numbers) from the set {1, ..., n}, what you want is the first k elements in a random permutation of [n]. The most elegant way to generate such a random permutation is by using the Knuth shuffle. See here: http://en.wikipedia.org/wiki/Knuth_shuffle

Answer 2

grab unique random numbers I ponder?

1. Make an array of N unique elements (integers in range 0..N-1, for example), store N as arraySize and initialArraySize (arraySize = N; initialArraySize = N)
2. When random number is requested:
   2.1 if arraySize is zero, then arraySize = initialArraySize
   2.1 Generate index = getRandomNuber()%arraySize
   2.3 result = array[index]. Do not return result yet.
   2.2 swap array[index] with array[arraySize-1]. Swap means "exchange" c = array[index]; array[index] = array[arraySize-1]; array[arraySize-1] = c
   2.3 decrease arraySize by 1.
   2.4 return result.

You'll get a list of random numbers that won't repeat until you run out of unique values. O(1) complexity.