Random shuffle

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)

        return pendingSongs.Dequeue();

Comments (19)

  1. nicgrave says:

    If I were to implement this, I'd go the route of most media players which is to generate the randomized list and never re-randomize it. This ensures that after reaching the end, you will continue on with a new song. It does mean the playlist itself repeats, but this is usually acceptable if not appreciated as it means you'll keep an even distribution of the same song playing again.

  2. ShawnHargreaves says:

    > I'd go the route of most media players which is to generate the randomized list and never re-randomize it

    That works nicely for media players which typically have hundreds of thousands of songs, so repeats are few and far between. In this game, though, we only had 12 songs to choose from, so I wonder if that repetition might become too obvious over a lengthy gameplay session?

  3. Simon Dufour says:

    I would have done this:

       Song PickRandomSong(song oldsong)


           Song nextSong = getRandomSong();

           while(nextSong == oldSong)

               nextSong = getRandomSong();

           return nextSong


    You won't play the whole tracklist all the time but the same song won't play twice in a row. A new song might pop in from time to time, even after an hour of gameplay. Your solution work too.

  4. ShawnHargreaves says:

    > while(nextSong == oldSong)

    This is vanishingly unlikely, but such algorithms always make me nervous as there is a theoretical chance this could never terminate!

    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 🙂

  5. Josh Jersild says:

    An implementation I did once, ages ago, was to keep a queue of "recently played" that is, say, a maximum of 3/4 the size of the total set, and a list of "available".  Choose a random song from avaialble, add it to the recently played queue.  if the queue is larger than the max requested size, dequeue the least-recently-played one and put it back into "available".  That keeps you from ever repeating a song in the near term (though it is possible, albeit somewhat unlikely, that some songs would never play at all).

    I think I eventually solved the "some songs might never play" thing, though I can't remember how now…I just remember the initial implementation.

  6. Scot Boyd says:

    I would want to avoid the peek every time, so I would add a param to the ShuffleIntoRandomOrder method specifying a song that should not be first, and then pass that when I need a reshuffle.

  7. Jeff says:

    The peek is minimal…only happens 1 time per song.

  8. Sludge says:

    // Always move forward through the playlist but do so unpredictably.  Note that this works best if there is no pattern to the songs

    // in the list in the first place and if allSongs.count is considerably less than MAX_SONG_SKIP

    int PickNextSong_Random( int currentSong )


      int nextSongIndex = currentSong.index + (rand() % MAX_SONG_SKIP);

      return nextSongIndex % allSongs.count;


  9. Erzengel says:

    Or, Scot, you can do the following:

    Song PickRandomSong()


       Song ReturnValue = pendingSongs.Dequeue();

       if(pendingSongs.Count == 0)


           pendingSongs = ShuffleIntoRandomOrder(allSongs);

           if(pendingSongs.Peek() == ReturnValue)



       return ReturnValue;


    But as Jeff points out, removing the peek is needless optimization. This is only being called when a song ends, so it only happens once every 3 minutes or so.

    I personally would do it this way so that there's no "lastSongPlayed" member variable needed (unless it's already used elsewhere). Might help in limited memory environments.

    This reminds me of one title a colleague worked on in QA. When choosing "random map", it would randomly select a map number. If the map wasn't unlocked yet, they used the default map (map 0) instead. So if you didn't have a lot of maps unlocked, you got map 0 90% of the time, and map 2-6 only appeared 2% of the time. While QA put in a bug for this, the team said they didn't care and closed the bug. I guess they didn't want to create a list of unlocked levels and choose from that? Or simply try again a few times before giving up?

  10. Raspofabs says:

    Wow, everyone sounds like they really want to solve this the "right" way ™….

    I think i'd just keep a list of the last N* songs played, and keep rolling until I don't have one of the songs.

    Concentrating on creating perfect code in situations like this wastes valuable brain cycles. Just find out what it is that the bug means (don't want to hear the same song in a while), and implement a fix for that problem.

    *where N = 30 minutes / average length of song

  11. ShawnHargreaves says:

    > I think i'd just keep a list of the last N* songs played, and keep rolling until I don't have one of the songs.

    But what if there are <= N songs in total?

  12. Roy Triesscheijn says:

    I love how this post proofs itself by looking at the comments 🙂

  13. Caleb Jares says:

    Here's a way to do it without guesswork. Just pretend the current song is AllSongs[0]. Then you can just offset it to get all the other songs (1 – TotalSongs).

    int lastSongIndex = 0;

    Song PickRandomSong()


    int random = rand() % (TotalSongs – 1) + 1; // so we don't get a 0

    lastSongIndex = (lastSongIndex + random) % TotalSongs;

    return lastSongIndex;


  14. dgschrei says:

    I'm more the kind of guy who would go with the easy fix.

    currentSong = 0;



       int nextSong = rand() * librarySize;

       if(nextSong == currentSong)

           nextSong = ++nextSong % librarySize;

       return nextSong;


    Sure it is no longer really random if it just chooses the next song in the library instead of repeating the same song, but it's quick to implement.

    It also could be incorporated into your second solution if you really wanted the option to only play a song again after the entire library had been played.

  15. drozzy says:

    This was a fun read 😉 Man, I really hate problems like these, where there is vague complexity – you can quite describe it but you just know that if you provide a solution, there WILL be a problem with it!

  16. James says:

    > 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 🙂

  17. Wade says:

    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.

  18. TOverbay says:

    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#.

  19. TOverbay says:

    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

Skip to main content