Music Algorithms – How Shuffle Works in Music Players

algorithmsrandom

I always hear how it is hard to implement shuffle algorithms for music players, but never really the explanation for it. What makes it hard?

Take for example how I would implement one:

  1. First the user adds 5 songs to a playlist 
    let songs = [0, 1, 2, 3, 4];
  2. Then the user enables shuffle
  3. The program would then copy the songs array into a new array, say shuffle
  4. Then the shuffle array would be randomly sorted with any algorithm
  5. The shuffle array is stored in eg. a text file for persistence, which is loaded at session start
  6. Let's say, the shuffle array is now [2, 4, 0, 1, 3]
  7. Then the player plays this array in reverse order

  8. When a song is played, it is removed from shuffle array. Eg.

    // shuffle starts as [2, 4, 0, 1, 3]
while (shuffle.length > 0) {
  player.play(shuffle[shuffle.length - 1]);
  shuffle.pop();
}

// First iteration plays song 3, and the array is then: [2, 4, 0, 1]
// The second plays song 1, and the array is then: [2, 4, 0]
// Third plays song 0, and the array is then: [2, 4]
etc.

  9. Then when all songs have been played, a new array would be again randomly generated from songs, which could have had new songs added to it. Maybe even say a couple of songs before the last one, so that the new array is ready by the time the previous one finishes.

  10. You could even stop play and resume later, and you would still only hear songs that have not yet been played, since they are not yet removed from shuffle

Even if someone has 20000 songs, the array would only be (given it references by integer index) a 125 KB file.

Best Answer

Shuffle is hard for music players because what people understand as random and what random actually means are two different things. The difficulty comes in matching user expectations. Users will say their expectation is songs randomly selected, but there are many things they don't want from a random selection. There is nothing really wrong with your outline for randomly shuffling a playlist, other than it doesn't really meet users expectations of shuffle.

  • Users don't want to hear the same song multiple times in a row.
  • Users don't want to the same artist/album played consecutively or too close together.
  • Users want to hear 1-2 songs from every artist/genre in their collection before repeats occur.
  • Random sequences that match established patterns are viewed as not random and disliked. This would be things like playing track 2 from albums A, B, C then playing track 3 from those albums, or playing track 1 from A, track 2 from B, track 3 from C. This would also be if songs followed a rock, country, rap, pop cycle or songs played in alphabetical order.
  • Over playing less liked artists or under playing favorite artists creates dissatisfaction.
  • Subsets of songs shouldn't be played in the same order as previous iterations. similarly the last X songs shouldn't be in the first X songs in the next iteration.

Users really want something like a curated playlist that cycles through their collection and plays songs semi-randomly along an equal distribution. This is a much harder task than simply picking a random song or ordering a collection randomly. Many of these can be handled because we have establish enough meta data about songs that it can be used and taken into account, but balancing them is a difficult task.

Related Topic