Random shuffle

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)
pendingSongs.Enqueue(pendingSongs.Dequeue());

return pendingSongs.Dequeue();
}```
• 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.

• > 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?

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

• > 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 :-)

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

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

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

• // 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;

}

• Or, Scot, you can do the following:

Song PickRandomSong()

{

Song ReturnValue = pendingSongs.Dequeue();

if(pendingSongs.Count == 0)

{

pendingSongs = ShuffleIntoRandomOrder(allSongs);

if(pendingSongs.Peek() == ReturnValue)

pendingSongs.Enqueue(pendingSongs.Dequeue());

}

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?

• Wow, everyone sounds like they really want to solve this the "right" way (tm)....

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

• > 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?

• I love how this post proofs itself by looking at the comments :)

• 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;

}

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

currentSong = 0;

ChooseNextSong()

{

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.

• 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!

Page 1 of 2 (19 items) 12