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.
grab unique random numbers I ponder?
- 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)
- 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.
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
An n-bit Maximal Period Linear Shift Feedback Register (LFSR) will cycle through all of its (2^n -1) internal states before an internal state is repeated. A LFSR is a Maximal Period LFSR if and only if the polynomial formed from a tap sequence plus 1 is a primitive polynomial mod 2.
Thus, an n-bit Maximal Period LFSR will provide you with a sequence of (2^n - 1) unique random numbers, each one of them is n-bit long.
A LFSR is very elegant.
Since you're imposing uniqueness, then a pseudorandom generator should be sufficient, which can be configured to not repeat for as long a sequence as you probably need. Eg, an LCG: if seed is uint32 and initially 0, then use (1664525 * seed) + 1013904223 for the next seed and take the low word for your unrepeated 16-bit result.
