|
Re: Replacing duplicates in a randomly generated array
Without looking through your solution, I'll make a few suggestions. This is also related to an interview question we give to SW interns.
One approach is to keep track of the numbers you've already used by searching and rejecting duplicates. This is actually a pretty bad approach as the execution time of your solution is now largely dependent on the behavior of rand(). In fact, with a sufficiently bad rand() or a large enough set of questions, your program may never finish.
A different approach is to build an index array from 1 to N where N is the number of problems to choose from and you want to randomly select M Problems from it. The first random number you generate is in the range of 1 to N inclusive. You remove that element from the index array and add it to your homework array. The index array is now N-1 in size, so you generate a random number from 1 to N-1, extract, and add it to homework array, etc. You continue to shrink the range of the random number and the index array at the same rate until you have extracted as many indices as you like -- M of them. The index array only ever contains unclaimed problems, the execution time is constant, no duplicates, etc.
Another approach is to make the index array and perform an inplace perfect shuffle on it. You may want to google perfect shuffle algorithm for exposure to some of them. Then take the first M. Note that this is pretty closely related to the previous approach.
Greg McKaskle
Last edited by Greg McKaskle : 30-07-2012 at 20:38.
Reason: typo
|