Random shuffle

Random shuffle

  • Comments 19

I am fascinated by problems that are easy to describe, and which appear simple when solved correctly, but where the implementation must contain surprising complexity in order to do what people expect.

Example: play a list of songs in a random order.

When I had to implement this feature for MotoGP, my first attempt was indeed simple:

    Song PickRandomSong()
    {
        return allSongs[GetRandomNumber() % allSongs.Count];
    }

A few days later, one of the testers filed a bug:

Symptom: when music is set to random, the same song is sometimes played twice in a row.

Expected: a different song should be chosen every time.

Dang it!  But this tester was quite right.  If I gave a stack of albums to a DJ and told him to play them in a random order, of course he would never play the same song twice in a row.  As is often the case, when we said "random" we actually had more specific requirements than just a sequence of independent random selections.

My second attempt was to randomize the entire list of songs in one go, like shuffling a deck of cards as opposed to repeatedly rolling a dice:

    Song PickRandomSong()
    {
        if (pendingSongs.Count == 0)
            pendingSongs = ShuffleIntoRandomOrder(allSongs);

        return pendingSongs.Dequeue();
    }

This version has two desirable properties:

  • Avoids playing the same song twice in a row
  • Every song is played once before any is repeated

But it still has a flaw.  After the entire list of songs has been played, we shuffle them again into a new random order, at which point it is possible the same song could be repeated.  That could be avoided by weighting the random selection, biasing it to pick songs that have not recently been played (although care must be taken not to make the bias too strong, which could force the songs to always repeat in the exact same order).  But I went with a simpler approach, far from mathematically elegant but good enough to get the job done:

    Song PickRandomSong()
    {
        if (pendingSongs.Count == 0)
            pendingSongs = ShuffleIntoRandomOrder(allSongs);

        if (pendingSongs.Peek() == lastPlayedSong)
            pendingSongs.Enqueue(pendingSongs.Dequeue());

        return pendingSongs.Dequeue();
    }
  • > Sure, it won't happen in practice, but I feel cleaner if I can find a way to avoid making such assumptions in the first place :-)

    I think for me the discomfort comes more from not trusting getRandomSong() to be truly random, after all I don't lose much sleep over the probabilistic guarantees we get from the error correcting codes used in our memory, disks, buses, and so on.

    I think your point about how a seemingly simple problem is actually complex, and that many apparently straightforward solutions have a range of behaviors and corner-cases speaks well to the difficulty inherent in software development. The crux of the issue seems to be that the problem is "seemingly simple", when in actuality it also appears to be quite ill-defined, hence all the different solutions.

    As far as the songs go, I think i'd also prefer not to hear the same song again even with one song in-between (reasonably probable with only 12 songs). My threshold is probably 3 or 4 songs :)

  • You could set up 2 random playlists.  The list you played would have 1/3 of the songs.  When it was done, you would take 1/3 of the songs from the not played list to play next, and put the songs from the played list in the not played list.  You would play at least 1/3 of the songs without a repeat.  You still might have a song that never plays.

  • If you use a prime number as your 'skip' number, and wrap around to the beginning of the list if you go past the end, you'll eventually hit all songs. The bigger the prime number, the more randomized the list will be. No extra 'songs already played' lists to track. It's pure math and rather elegant. Mike McShaffry has a decent C++ implementation in his book "Game Coding Complete" I translated it to VB a couple of years ago. Shouldn't be too hard to translate to C#.

  • A couple of caveats to this method: 1) don't use a skip number that is exactly the same as the number of songs in your list. 2) don't use 2 as your skip number... it only works on lists with an odd number of songs.  ;p

Page 2 of 2 (19 items) 12
Leave a Comment
  • Please add 4 and 4 and type the answer here:
  • Post