TechnicalArchitectureWorx

The (Unofficial) ITWorx Technical Architecture Blog

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?

6 Responses to “Interviewing Question: How can I randomize without recurrence?”

  1. IDEA: Maintain an array of not-yet-played tracks. When a track is played, remove it from the array. Select a random number between 0 and n-1 to determine next played track.

    0. Assume n is the number of music tracks.
    1. Create an array called A, with n elements. Init each element, such that A[i] = i
    2. Pick a random number, r, between 0 and n – 1. r is array index of next track to play; next track to play is A[r].
    3. Remove A[r] and move elements after it up to fill hole; copy elements A[r+1] thru A[n-1] to a[r]. Since array elements are stored contiguously, you can use MemMove() so it will be fast.
    4. n = n – 1 since there is one fewer tracks.
    5. Goto step 2 until n = 0.

  2. archworx said

    My solution would be to slice the playlist into zones and then randomize within each zone. The algorith will make sure that each zone is played and the tracks insiden it will be played in random.
    This technique might not eliminate starvation all together, but I think it would greatly reduce it, since tracks will be played in all zones.

    MSamy

  3. MSamy, you are basically selecting the random track based on two random numbers instead of one. I guess this would be more random, but you are still at the mercy of the random number generator, which is none too good to begin with if you’re even talking about this problem. I guess I view this as a stop gap solution with ultimate limitations.

    I would just get a better random number generator! I have had great results using the CryptGenRandom() function. It’s way better than the VC++ rand() function.

    — David

  4. archworx said

    This is a great discussion, which is healthy because it illustrates diversity of ideas. This is a key step to going up from a level-2 solution to a level-3 solution.

    – mkaram

    P.S. Thanks to David Ching for being a noteworthy contributor to these discussions.

  5. Mohamed Fouad said

    Weighting groups and randomization priority for least weighted group. Wallaho 2a3alam!

  6. InnovationHero said

    a chaos theory API would be nice =)

    http://www.imho.com/grae/chaos/chaos.html

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

 
%d bloggers like this: