3

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.

  • 1
  • I checked that one too, but in that the use case is far more specific, ie. playing a similar version (eg. various live performances of the same song) of the same song only after a certain amount of other songs have played inbetween. – Juha Untinen Jul 25 '18 at 11:31
  • 8
    Implementing shuffle correctly is, indeed, pretty trivial. Implementing shuffle that "feels randomish" to people isn't, because a random shuffle will randomly repeat sub-sequences on different plays, or randomly select clusters of songs from the same album. The listener, noticing these patterns, will attribute them to a "bad" shuffle because people are rubbish at reasoning about coincidences. – Useless Jul 25 '18 at 12:10
  • 1
    Oddly, a computer is better equipped to determine randomness of a series than a human being. It seems what we really want is "pseudo-random" shuffles. – Neil Jul 25 '18 at 12:35
  • Here is a more visual representation of why simply shuffling a playlist fails the human's "looks random" test. Also known as Texas sharpshooter fallacy. – Lie Ryan Jul 30 at 10:33
13

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.

3

In your 5 songs example almost 59.3% of shuffles will result in two adjacent songs being played in order.

To the listener this will seem non-random.

Add to that, how do you decide when to reshuffle? If the user switches the device off and on again will the device reset the 'already listened to' list?

But I think the main reason is skipping. The user will skip the songs they don't like, proceeding through the shuffled list much faster than if they were forced to listen to each song.

This means they are likely to have 'Why does it always choose Roxette?!??!' more often temporally than copies of 'it must have been love' occur ordinarly in your shuffled list*

*4/5 you have to have the original swedish, unplugged, live and extended editions

  • Hmm, you're right. Then it would indeed need to check some metadata too in the sorting. Maybe first randomize the shuffle order by the first character in the Artist's name, and then randomize shuffle again by the index - possibly with a different algorithm? – Juha Untinen Jul 25 '18 at 13:13
  • 1
    @JuhaUntinen: The second shuffle undoes the first shuffle. The issue outlined here is effectively an inverted multidimensional traveling salesman problem, where you want trips between stops to take as long as possible (on average). – Flater Jul 25 '18 at 13:20

protected by GlenH7 Jul 30 at 12:00

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.