Interview Question
Country: United States
This is a classic phone screen question. Leo's solution is the classic answer. If the first element isn't drawn on the first iteration, you want to keep it as a candidate, hence the swap. (And the swap also effectively removes the just-chosen number as a candidate, and adds it to the result set, effectively killing three birds with one stone.)
If you can process each number on the fly (by outputting them, using them directly, yielding them from a coroutine, appending to a passed in collection, or calling back a callback function), then replace the swap with a simple assignment of a[r] = a[i], since you won't need to revisit the value of a[i] after emitting it.
Guys, you did not read.
=======
write a program to Generating Random Integer numbers without repetition
======
You need a GUID generator, not any random no generator. Any computerised random generator are bound to repeat, not because they are not random, but because they have a finite integer range.
One simplest solution is :
Generate sudo random number, using any methods(such as linear congruential generators, Fibonacci generators), or can use inbuilt method. call it x
hash it, if already present then try again, otherwise store it in array, and set hash function true.
Obviously here we require O(n) space, and they will not be following uniform distribution.
How about a sudoku random number? After all, repeats are disallowed in any square, any row, and any column. Problem solved!
@showell : If the numbers have any kind of relation between them, then they are not random, the term random is define in this way that we can't predict them, they can't follow any pattern even when some one draw infinitely many,
Now there is no way to generate perfect random number, all random number generator(I mentions above), generates only sudo random numbers, but as our computer are not powerful enough to find any patterns in these sudo random numbers, so we generally accept them.
Assume generate m random intgers from n intgers, it can shuffle the first m elements.
- Leo March 16, 2013