I read an article the other day explaining that Spotify changed it shuffling algorithm due to a large amount of user feedback suggesting it was repeating songs by the same artist frequently or playing the same song twice. A company like Spotify has a huge amount of engineering talent, so I was confused as to how an algorithm as simple as shuffle wasn’t correct. I did a little research into this issue and what I found was quite interesting.
How to Shuffle Randomly – The Fisher Yates Shuffle
Historically speaking Spotify used a shuffle function that was completely random, they did this by using a famous algorithm called the Fisher-Yates Shuffle. Lets start by examining how this algorithm works.
Lets say we have an array of numbers.
Firstly I randomly pick the array position containing the value 8 and I place that into the first position in a new array.
Now I have less numbers in the original array and pick again
And so on until the original array is empty and the new array is complete. This however isn’t entirely efficient as it means I have two arrays and are therefore using more memory.
Because of this a variant of this algorithm was made which decided not to put items onto a new list, but instead swapped them with the last item in the array not yet touched. This would work as follows.
We start with our original array.
We then take the random position taken and swap it with the last position of the array. This switch demonstrated below
From
To
We now repeat the process but make the range one element smaller – in this example 8 will always remain the last value in the array.
And this process repeats until the random range is 1 item. Giving you a randomly sorted array.
This process is the modern Fisher Yates shuffle.
Coding the Fisher Yates Shuffle
Lets code the fisher yates shuffle.
The method is quite simple – we receive an array of generic items and a random number generator. We then loop through the array in reverse order, at each position we pick a random number between 0 and the current position. We then get the item in the random position and swap it with the remaining last position, exactly as explained earlier.
If we call this method as follows.
the output of the console is.
And as you can now see our array is shuffled.
So why wasn’t this working at Spotify?
Well… it was. If I can code something like this in 10 minutes, I doubt it takes the talent at Spotify 2 minutes. They were randomly shuffling music playlists. What caused the complaints they received is how people perceive randomness Vs what randomness actually is. This misconception is often stated as the Gamblers Fallacy
Imagine if I flip a coin – we know there is a 50% chance of it landing on heads and a 50% chance of it landing on tails. But what if I flip a coin and it lands on heads 3 times in a row? surely next time it must be tails right?
WRONG
the probability is always 50% of heads.
Now imagine a lottery draw – If I was to select numbers 1,2,3,4,5,6 – the shop attendant would laugh at me saying “there is no way that is gonna happen”, but the probabilities of that combination winning are no different to the probabilities of any other 6 number combination – we just assume its much less likely as we see some kind of order in it.
So in Spotify’s case they randomly shuffled playlists, and sometimes songs by the same artist were next to each other – this is to be expected the probability of a song appearing in a given position is fixed, in the same way that flipping a coin twice and getting two heads in a row is fixed. Each song in the list has an equal probability of being played next. However to the user this didn’t seem “random” despite the fact it was.
Does a user want random selection?
The term shuffle is closely associated with a deck of cards, and if you consider shuffling an array of items it is pretty much the same process as shuffling cards. If you start with 52 playing cards in a specific order you shuffle them into a random order, this is done so the card game played has an element of chance. But with regard to music playlists I personally feel shuffle and random mean different things to the user listening to music.
Random is where your next song is selected arbitrarily. It’s then returned to the list and another selection is made. If The song you just listened to is also considered and the selection of the next song is performed randomly, it then follows that depending on the number of songs you have in your list, it’s likely one song can come up repeatedly.
For example if you have Track A, Track B and Track C in your playlist, chosen at random, there is 1/3 chance A could be played. After this song finishes you still have a 1/3 chance A would be played again (if it isn’t removed from the collection).
When you press the shuffle button, you don’t mean you want a random selection, what you mean is “Play me the songs in my playlist in no particular order” but you don’t want to hear one song or artist repeatedly in a row. The selection process you actually want is not random but it feels “more random”.
What Options are There?
When I started this post I did think it would be a simple exercise showing a famous computer science algorithm, however I didn’t realise that this was such a specialist topic. There are literally hundreds of approaches used to create a “good music shuffle”, these are as much to do with behaviour science as they are to do with programming
Merge Functions
The first question to ask is what is it we perceive is similar about songs that makes us feel the selection wasn’t “shuffled enough”. we need some property of a song that groups them together as similar.
This itself is a huge problem as musical genres have crossover and genres themselves can be VERY specific, for example when someone says they like Jazz do they mean acid jazz, swing jazz, bebop jazz, New Orleans jazz etc..
While far from perfect for the purposes of explaining ways these shuffles could be implemented I will use a “genre” of music to try to separate similarity, this is simplifying the issue but it will show how these approaches could work.
Lets say we have the following songs in a playlist
| Song ID | Song Title | Artist | Genre |
| 1 | Smoke on the Water | Deep Purple | Rock |
| 2 | Bohemian Rhapsody | Queen | Rock |
| 3 | Back in Black | AC/DC | Rock |
| 4 | Thunderstruck | AC/DC | Rock |
| 5 | Paranoid | Black Sabbath | Rock |
| 6 | Born to Run | Bruce Springsteen | Rock |
| 7 | Moonlight Sonata | Beethoven | Classical |
| 8 | Raindrop Prelude | Chopin | Classical |
| 9 | Concrete Schoolyard | Jurassic Five | Hip Hop |
| 10 | Sucker MCs | Run DMC | Hip Hop |
| 11 | Fight the Power | Public Enemy | Hip Hop |
If we were to create a grouping so similar songs are placed together (we are using genre) into a separate collection. We would have something like this.
We can see our playlist is probably from a fan of rock music. The challenge we have is to try to not play too much rock music in a row to make it feel like a good shuffle.
Firstly lets shuffle each individual groups to reduce the probability of each group having the same band playing next to each other within a group (AC/DC could have this possibility).
Now we want to spread our collection to evenly space songs. In effect we will make each collection the length of the largest group and have the values spaced at regular intervals. Taking our example we could do something like this.
We could now work column by column. Ignoring the blank spaces and randomising the columns before pushing these sub collections to the output playlist.
So for example with the first column. we could shuffle 5 and 8 and push that to the output.
Then column two (11 and 2)
and then column 3 we only have one choice (id 6)
and so on…
One output of the completed list to be played could be the one shown below;
I know what you are thinking here “but that’s two rock songs in a row! TWICE!”, yes that is true, but in this example I have a much higher proportion of rock songs in the playlist compared to anything else, so it is unavoidable.
I am also possibly oversimplifying the grouping concept and operating on a very small playlist as an example of one way this issue could be resolved. There is no perfect solution here, but this is potentially more favourable to a user than a pure random selection as we are trying to space our groupings out evenly but with randomness.
Coding the Merge
This is not the most optimised way of performing this operation, but it hopefully demonstrates a clear and easy to understand way in which such a procedure could be coded.
Step One – The Song Class
Firstly lets make a class which contains properties about each song.
As you can see each song will have a track Name, artist and genre.
Step Two – The Song Bank
Now we need to make a collection of all of the songs available to be picked we can create a method called createSongBank that returns this array.
Step Three – Grouping and Shuffle
From our songs in scope (the songBank array) we need to now make different collections for each grouping (we are going to group by genre). We can create a function that receives a genre and returns an array of that genre from the song bank.
for each of the genre’s we can then shuffle them using the fisher yates shuffle method we wrote earlier in this post.
Step Four – Creating Collections and Spacing
At this point we have one array for each of our groupings. We now need to establish which grouping has the most songs and resize all the arrays to that length, if the songs need spacing across the array we also need to do that. The following method achieves this;
I establish the longest collection of songs and then if you are not the longest list (which needs no repositioning) I spread the songs using the spreadSongs method.
Spreading the songs could be done any number of ways, the tricky part is that you might have a number of songs that does not divide evenly into the array length. If we have 7 songs to spread across an array of 10 elements we cannot do this evenly.
The way I handle this is if there is not a whole number generated by dividing items that need to be spread by the available position (an even distribution). I put the item in the first available slot, adjust the no of items to move and positions available and continue until there is an even distribution that can be placed. For example;
This would result in an output array spread as follows;
Where the yellow elements represent the divides which are not whole numbers and the green ones represent where an even distribution can be made (once every 2 elements). This is handled in the spreadSongs method
Once an even distribution can be placed (it could be possible from the start – for example 5 songs into an array of 10 elements) the evenlySpreadItems method is called.
Step Five Selection – Creating The Playlist
At this point we have out grouped elements spread and need to shuffle the columns. before returning one list of songs to play. This can be performed as follows
Executing the Merge
we can code a method to perform all these steps and output the shuffled array.
The console output of this is as follows;
in theory we now have a better distributed playlist!
Rule Based Selection
One other possible approach would be to use a series of rules for what can be next in the playlist. While researching this topic I came across this flow diagram (Speed of Sound Magazine).
Ultimately this approach is to have a function that evaluates whether the proposed next song is appropriate or not. I do think it has some flaws (if you had an entire playlist made of one artist it would return nothing for example!) but the concept is a valid one. you could have a function that evaluates if the next song to be played is appropriate or note.
Creating a Function
Lets make a new class named SongPlayer. It will have properties of a SongBank a FilteredSongBank a current Song and a next song;
we will need a method of fetching a random song from the filtered bank (as we will be removing songs from the full list if they are invalid)
We will also need a way of evaluating if the random song selected is valid or not (not the same genre or artist).
If the song is invalid it is removed from selection at this point – however if the selection is valid all songs are included for the next selection.
As referenced above there is a method to remove a song from the filtered list
these methods/functions are called from the getNextSong method.
Executing the Function
We can call this function from the SongPlayer object as follows.
and example output is shown below.
Conclusion
Its funny how something so basic can escalate so quickly. As mentioned previously this is an issue that in part is more to do with human perception and behavioural science than it is to do with programming. I suspect the shuffle functions of music providers gets perfected over time, possibly with end user trials and focus groups. I’m not sure whether there is an “optimal” approach, all possible approaches would require classification on some level to signify what music is “similar enough” to avoid playing in succession, and with something as subjective as music that isn’t grouping isn’t that easy. I am sure all music lovers have had debates along the lines of “They aren’t really a rock band!” or “this is more techno than hard house”.
Not only this the challenge for engineers is to take these concepts and code something which isn’t very computationally expensive (as for a service like Spotify this function will be called millions of times per day).
The Spotify Engineering page for how they changed their algorithm is: How to shuffle songs? – Spotify Engineering. I recommend reading this as their approach is different to the two I highlighted, it is somewhat of a highly optimised version of the merge function I mentioned. I would have never appreciated the effort went into ordering a playlist had I not read this.
The code relating to this blog is in GitHub: Non random shuffles for Music players. (github.com)