Imagine you have a list, a playlist if you will. Playlist with limited amount of entries in it. How could you make a music player keep playing this playlist for an indefinite amount of time?
Given an array playlist = [a, b, c, d]
This strategy is suboptimal, since we are trying to avoid repetitive playback.
Lets start with the same array.
playlist = [a, b, c, d]
shuffledArray = [b, d, c, a]This is an improvement, but we are going to run into a problem with this approach. Say, we do a multiple passes with this algorithm.
shuffledArray = [c, a, d, b]shuffledArray = [b, a, d, c]If we play the Pass #2 output right after Pass #1 output, the song "b" is going to queue twice in a row (songQueue=[c, a, d, b, b, a, d, c]). While this is a worst case scenario, this is still a very likely side effect of this algorithm.
Less worse (but still pretty bad) cases include:
songQueue = [..., b, a, b, ...]songQueue = [..., b, d, a, b, ...]songQueue = [..., b, c, d, a, b, ...]Note: A song being repeated with 3 tracks in between is guaranteed to happen when working with only 4 elements, but as playlist size is scaled up, the probability of a track repeating too soon stays disproportionately high.
Let's start with an array of 6 elements this time.
playlist = [a, b, c, d, e, f], songQueue = []
Let's pick an element at random from the first two elements of playlist array and add it to the songQueue.
randomSongElement = random.choice(playlist[0], playlist[1]) //randomSongElement="b" We need one more step to complete a cycle of this algorithm: remove the chosen element from
songQueue.push(randomSongElement) //songQueue=[b]playlist array and append it at the end.
playlist.remove(randomSongElement) //playlist = [a, c, d, e, f] Finally, repeat all of the above.
playlist.push(randomSongElement) //playlist = [a, c, d, e, f, b]
Now, since the "b" element is at the end of the array, the current algorithm will ensure that at least n-2 songs are played after the song "b", before it's queued again in the player, n being the length of the playlist array. This guarantees to queue 14 unique tracks, in a playlist of 15 songs. To hear the 15th, you MUST get through at least one repeating track. Additionally, if we were to pick between 3 items at random, it would give us n-3 songs and so on.
Since these radio stations are roughly 1 hour in total duration, this gives the listener about 55 minutes of playtime before they hear something they've already heard. The beauty of this algorithm is how perfectly it fits this use-case. When a listener is finished, they won't stick around after 1 hour, because they have just now heard all these songs. They will leave and hopefully come back in a day or so. After this amount of time, due to the probabilistic nature of this algorithm, the playlist order will look nothing like what they heard a day ago. To demonstrate, let's go through a few iterations of this change together.
[a, b, c, d, e, f] //heads (we pick the first element)
[b, c, d ,e, f, a] //tails (we pick the second element)
[b, d, e, f, a, c] //tails
[b, e, f, a, c, d] //heads
[e, f, a, c, d, b] //heads
[f, a, c, d, b, e] //tails
[f, c, d, b, e, a] //heads
[c, d, b, e, a, f]
As you can see, after a several iterations, the list looks nothing like the original. We have preserved the guarantee that a song should repeat as infrequently as possible, while adding inherent randomness to the process that will keep the listener guessing.