Interviewing Question: How can I randomize without recurrence?
Posted by archworx on February 6, 2007
Suppose I have an application that plays the audio files on my play list, and supports playing them in a random order. More often than not, this kind of application will employ a Psuedo-Random Number Generator. Which is great, except that these kinds of generation algorithms tend to be not exactly random sometimes. This becomes a problem when the algorithms are so bad that starvation occurs. With starvation you get some tracks that are played over and over again, and others which are almost never played. One way to fix this is by further warping the “randomness” of the Psuedo-Random sequence to try to make sure that every track is played once and only once before it is ever replayed.
How would you implement this in code, as a first hack?
How would you implement this efficiently?