We can’t do all this shuffling when the track is requested, because it would create disproportionate transition times between tracks, among other obvious problems.
We remedy this by creating a permutation of tracks whenever the playlist is loaded up.
Count the number of tracks, and shuffle once for every track, abiding by the rules set in v2, until we have a permutation of “random” tracks.
The larger the playlist, the less likely we are to re-shuffle, and an average album is 15 tracks long.
def shuffle_v2_1(playlist): """ Implements v2, but generates the entire permutation before playing anything.
This reduces the disproportionate wait times between shuffles by offloading it to the initial playlist load.
Users won't really care if it takes an extra second to load a CD, but they will care if there's a load time between tracks.
:param (dict) playlist: Dictionary of track information, including the track data.
:return (list): Permutation of tracks to shuffle through.
""" track_permutation = [] current_position = int(playlist['Meta Data']['Current Position']) playlist_length = int(playlist['Meta Data']['Length']) if playlist_length in [0, 1]: return [0] # An empty, or small playlist while len(track_permutation) < playlist_length: shuffle_position = randint(0, playlist_length – 1) delta_position = abs(shuffle_position – current_position) if shuffle_position not in track_permutation: if playlist_length > 2 and delta_position == 1 and random() < 0.
5: shuffle_position = randint(0, playlist_length – 1) elif playlist_length > 2 and delta_position == 2 and random() < 0.
25: shuffle_position = randint(0, playlist_length – 1) track_permutation.
append(shuffle_position) return track_permutationSo, we’ll say that the average number of times we’d reshuffle is the number of indices we’d reshuffle times their probabilities.
If we say that the neighboring 1st, 2nd, and 3rd index reshuffle with a probability of 100%, 50%, and 25%, respectively, we’d reshuffle about (1/15)(1) + (1/14)(0.
5) + (1/13)(0.
25) = 0.
12 = 12% of the time.
We’ll call that our benchmark.
Let’s not do worse than a 12% re-shuffle rate.
Shuffle v2.
2: Final ImplementationMathematics is the art of giving the same name to different things.
— Henri PoincareWe take v2.
1 and generalize the probability of reshuffling for n tracks in playlist p.
We say that the probability of reshuffling is 1 / delta_position, giving us a scalable probably set for all tracks in the playlist (instead of just the two neighboring indices).
def shuffle_v2_2(playlist): """ Implements v2.
1 but generalizes the probability of reshuffling.
:param (dict) playlist: Dictionary of track information, including the track data.
:return (list): Permutation of tracks to shuffle through.
""" track_permutation = [] current_position = int(playlist['Meta Data']['Current Position']) playlist_length = int(playlist['Meta Data']['Length']) if playlist_length in [0, 1]: return [0] # An empty, or small playlist while len(track_permutation) < playlist_length: shuffle_position = randint(0, playlist_length – 1) delta_position = abs(shuffle_position – current_position) if shuffle_position not in track_permutation: if playlist_length > 2 and random() < float(1 / delta_position) : shuffle_position = randint(0, playlist_length – 1) track_permutation.
append(shuffle_position) return track_permutationAn added bonus is that, by default, the probability of reshuffling goes to zero as delta_position goes to n.
All together, we get what I consider to be a rich, user-oriented implementation of the shuffle feature on music players.
Take note, Ford.
Performance of Our Playlist PermutationsWhat people fear most about tragedy is its randomness — a taxi cab jumps the curb and hits a pedestrian, a gun misfires and kills a bystander.
Better to have some rational cause and effect between incident and injury.
And if cause and effect aren’t possible, better that there at least be some reward for all the suffering.
— Jeffrey KlugerLet’s try to generalize the performance of this shuffle algorithm.
As the length of the playlist goes to infinity, the probability of reshuffling goes to zero.
The average performance is O(n), where n is the length of the playlist since it must go through all the indices of the playlist to order them.
For small playlists, performance is actually worse than O(n), as the probability of reshuffling is high.
There are only two real playlist sizes to concern ourselves with: EPs (1–3 tracks) and Albums.
For EPs, what will probably happen most of the time is that the first track will shuffle to the third track, finishing off with the second track.
This “waterfalling” behavior can actually be observed with playlists of any length, since the probability of reshuffling gets smaller the farther away from the initial track you are.
Appendix: Personal PreferenceI am fully aware that some people don’t care about this as much as I do, but I listen to a lot of music, and it frustrates me when I shuffle to the next track only to have the neighboring track play.
If I wanted the next track in the album, I wouldn’t have enabled the damn shuffle feature, Ford.
Moreover, it’s obvious at this point that I wrote this is a hate-fueled rage.
I don’t want to listen to Vietnow, I want something else!.On the plus side, I now have sample code to refer to when I come around to building my shuffle-oriented Spotify competitor!.