It’s probably no surprise that we take software algorithms for granted on a daily basis, but so much of computer science curriculum is focused on the classical algorithms, like sorting and search. Meanwhile, a lot of the focus in the corporate space is on really niche leetcode-style problems. It’s not often that you actually have to think about more interesting day-to-day algorithms like shuffling a playlist. That’s what I want to talk about today!
Table of Contents
Spreading the Joy of Coding
One of the best parts of my job as an educator is that I get to turn students’ interests into lifelong passions. After all, learning can be really hard, and we can do a lot as educators to alleviate some of that stress to prevent folks from leaving the field.
One way that I’ve put my beliefs into practice most recently is through something I’ve deemed the “pilot project”—though I plan to refer to it as the portfolio project in the future. In this pilot project, I’ve tasked students with developing their own APIs for things that they care about. Our course provides a ton of constraints, so students don’t really have to worry about being innovative. They just have to transfer what they’ve learned to a domain of their choice.
Over the course of the semester, I have learned so much about my students interests as a result. For example, here are just a few of the ideas my students had:
- A wildlife tracker
- A fantasy sports tracker
- An adblocker for RSS feeds
- A DHCP server
- A perfect number utility
- A fitness tracker
- A trading card library
- A game state saving utility
One student in particular was putting together a music playlist component. Naturally, this kind of component is seen in many tutorials, but I had a lot of fun reading through their design. One particular idea caught my attention: the idea of shuffling a queue of songs. Because they didn’t really have a solution for the problem, I got to brainstorming some algorithms to try to help them out. Naturally, this serves as the inspiration for the remainder of the article.
Modeling a Music Playlist
Before we can really talk about shuffling, we need to consider how one might go about modeling a playlist. Because a playlist is really just a list or queue, there’s not really a lot we have to do to model one. However, we should probably model the items that will go in the playlist. And because I love me some Python, I’m going to use it for my exploration today. To start, here’s a simple song model:
from dataclasses import dataclass @dataclass class Song: title: str artist: str album: str track_number: int
Now, I tasked my students with developing their own complete data structures. However, just to get to the interesting part of this article that covers shuffling, I’m going to use a Python list directly. Something like this could be my playlist:
playlist = [
Song("There, There", "The Wonder Years", "The Greatest Generation", 1),
Song("Passing Through a Screen Door", "The Wonder Years", "The Greatest Generation", 2),
Song("We Could Die Like This", "The Wonder Years", "The Greatest Generation", 3),
Song("Dismantling Summer", "The Wonder Years", "The Greatest Generation", 4),
Song("The Bastards, the Vultures, the Wolves", "The Wonder Years", "The Greatest Generation", 5),
Song("The Devil in My Bloodstream", "The Wonder Years", "The Greatest Generation", 6),
Song("Teenage Parents", "The Wonder Years", "The Greatest Generation", 7),
Song("Chaser", "The Wonder Years", "The Greatest Generation", 8),
Song("An American Religion (FSF)", "The Wonder Years", "The Greatest Generation", 9),
Song("A Raindance in Traffic", "The Wonder Years", "The Greatest Generation", 10),
Song("Madelyn", "The Wonder Years", "The Greatest Generation", 11),
Song("Cul-de-Sac", "The Wonder Years", "The Greatest Generation", 12),
Song("I Just Want to Sell Out My Funeral", "The Wonder Years", "The Greatest Generation", 13)
]
Wonderful! Our playlist is one of my favorite albums of all time in order. Maybe it’s about time we shuffled the order a bit.
Drawing Inspiration from Card Shuffling
In my students’ solution, they had left their shuffle algorithm blank because they just weren’t sure how they would go about shuffling a queue. Funnily enough, I also didn’t know how to shuffle a queue, so I got to thinking about it. Maybe, we just model shuffling in the same way a magician might shuffle cards. In other words, move half the songs into a second queue and pull from the front of each queue to form a third queue. Here’s what that might look like in code:
def shuffle(playlist):
half_size = len(playlist) // 2
left, right = playlist[:half_size], playlist[half_size:]
playlist.clear()
while left and right:
playlist.append(left.pop(0))
playlist.append(right.pop(0))
playlist.extend(right)
And, here’s the list you would get if you shuffled it using this algorithm:
[ Song(title='There, There', artist='The Wonder Years', album='The Greatest Generation', track_number=1), Song(title='Teenage Parents', artist='The Wonder Years', album='The Greatest Generation', track_number=7), Song(title='Passing Through a Screen Door', artist='The Wonder Years', album='The Greatest Generation', track_number=2), Song(title='Chaser', artist='The Wonder Years', album='The Greatest Generation', track_number=8), Song(title='We Could Die Like This', artist='The Wonder Years', album='The Greatest Generation', track_number=3), Song(title='An American Religion (FSF)', artist='The Wonder Years', album='The Greatest Generation', track_number=9), Song(title='Dismantling Summer', artist='The Wonder Years', album='The Greatest Generation', track_number=4), Song(title='A Raindance in Traffic', artist='The Wonder Years', album='The Greatest Generation', track_number=10), Song(title='The Bastards, the Vultures, the Wolves', artist='The Wonder Years', album='The Greatest Generation', track_number=5), Song(title='Madelyn', artist='The Wonder Years', album='The Greatest Generation', track_number=11), Song(title='The Devil in My Bloodstream', artist='The Wonder Years', album='The Greatest Generation', track_number=6), Song(title='Cul-de-Sac', artist='The Wonder Years', album='The Greatest Generation', track_number=12), Song(title='I Just Want to Sell Out My Funeral', artist='The Wonder Years', album='The Greatest Generation', track_number=13) ]
Which, works surprisingly well to me. Thankfully, because we’re keeping track of track number, it’s also very obvious how this algorithm worked; the second half of the playlist is interleaved between the first half.
Surely, professional magicians can actually do this and know the outcome of the resulting deck. For instance, we know the front song will always be at the front. No amount of shuffling will change that, nor will the last song ever move away from the end.
Also, I assume there is a number of shuffles that will result in the deck being sorted again. Upon testing, I was able to get the deck in its original order after 10 shuffles. Perhaps even more interesting, 5 shuffles gives the deck in reverse order—at least between tracks 2 and 12.
At any rate, in casual play among friends, you probably expect a bit more randomness. As a result, here’s the same algorithm, but we decide which list to pop from first based on the flip of a coin:
import random
def shuffle(playlist):
half_size = len(playlist) // 2
left, right = playlist[:half_size], playlist[half_size:]
playlist.clear()
while left and right:
if random.randint(0, 1):
playlist.append(left.pop(0))
playlist.append(right.pop(0))
else:
playlist.append(right.pop(0))
playlist.append(left.pop(0))
playlist.extend(right)
Surely, there’s a cleaner way to write this, but I just wanted to get something working. Here’s a result:
[ Song(title='Teenage Parents', artist='The Wonder Years', album='The Greatest Generation', track_number=7), Song(title='There, There', artist='The Wonder Years', album='The Greatest Generation', track_number=1), Song(title='Passing Through a Screen Door', artist='The Wonder Years', album='The Greatest Generation', track_number=2), Song(title='Chaser', artist='The Wonder Years', album='The Greatest Generation', track_number=8), Song(title='We Could Die Like This', artist='The Wonder Years', album='The Greatest Generation', track_number=3), Song(title='An American Religion (FSF)', artist='The Wonder Years', album='The Greatest Generation', track_number=9), Song(title='Dismantling Summer', artist='The Wonder Years', album='The Greatest Generation', track_number=4), Song(title='A Raindance in Traffic', artist='The Wonder Years', album='The Greatest Generation', track_number=10), Song(title='Madelyn', artist='The Wonder Years', album='The Greatest Generation', track_number=11), Song(title='The Bastards, the Vultures, the Wolves', artist='The Wonder Years', album='The Greatest Generation', track_number=5), Song(title='The Devil in My Bloodstream', artist='The Wonder Years', album='The Greatest Generation', track_number=6), Song(title='Cul-de-Sac', artist='The Wonder Years', album='The Greatest Generation', track_number=12), Song(title='I Just Want to Sell Out My Funeral', artist='The Wonder Years', album='The Greatest Generation', track_number=13) ]
Naturally, this algorithm is a bit nicer in that we’re not guaranteed to have the same first element. Unfortunately, it still suffers from having the last element stuck last, at least for odd length playlists. I’m sure there’s an easier solution to that, but I’m just happy this works!
And of course, just out of curiosity, I decided to shuffle the playlist until it was sorted again. Spoiler alert: it takes an extremely long time. In fact, it took 158,013,035 iterations to converge. I even did the following for my own sanity:
shuffle(playlist)
i = 1
while playlist != playlist_ref and len(playlist) == len(playlist_ref):
shuffle(playlist)
i+= 1
Perhaps I can speed things up by not using pop, but that would ruin the fun.
An Alternative Solution
One solution that my student came up with was to move the queue into an array, shuffle, and move the contents back. This may seem like a silly strategy. After all, why move all your data to a different data structure just to move it back (though looking back, my solution moves data around a bit too), but the reality is that arrays lend themselves really well to this kind of task. Luckily, Python lists are functionally arrays, so we can implement a random shuffling algorithm with ease:
import random
def shuffle(playlist, num_swaps=50):
swap_count = 0
while swap_count < num_swaps:
first = random.randint(0, len(playlist) - 1)
second = random.randint(0, len(playlist) - 1)
playlist[first], playlist[second] = playlist[second], playlist[first]
swap_count += 1
Surely, there are wasted swaps as we roll two of the same number, but it otherwise does a really great job. Here’s the result after using the default number of swaps:
[ Song(title='We Could Die Like This', artist='The Wonder Years', album='The Greatest Generation', track_number=3), Song(title='Chaser', artist='The Wonder Years', album='The Greatest Generation', track_number=8), Song(title='A Raindance in Traffic', artist='The Wonder Years', album='The Greatest Generation', track_number=10), Song(title='Cul-de-Sac', artist='The Wonder Years', album='The Greatest Generation', track_number=12), Song(title='Passing Through a Screen Door', artist='The Wonder Years', album='The Greatest Generation', track_number=2), Song(title='There, There', artist='The Wonder Years', album='The Greatest Generation', track_number=1), Song(title='An American Religion (FSF)', artist='The Wonder Years', album='The Greatest Generation', track_number=9), Song(title='Madelyn', artist='The Wonder Years', album='The Greatest Generation', track_number=11), Song(title='The Devil in My Bloodstream', artist='The Wonder Years', album='The Greatest Generation', track_number=6), Song(title='Teenage Parents', artist='The Wonder Years', album='The Greatest Generation', track_number=7), Song(title='The Bastards, the Vultures, the Wolves', artist='The Wonder Years', album='The Greatest Generation', track_number=5), Song(title='I Just Want to Sell Out My Funeral', artist='The Wonder Years', album='The Greatest Generation', track_number=13), Song(title='Dismantling Summer', artist='The Wonder Years', album='The Greatest Generation', track_number=4) ]
I’m sure there is an optimal number of swaps that’s a function of the length of the playlist. Regardless, I’m very pleased with the result.
Problem Solving Is Fun
If there is anything I’ve taken away from this exercise—aside from the fact that educators have a lot to learn from their students—it’s that solving problems on your own can be a lot of fun. I was able to get from concept to proof-of-concept extremely quickly. I hope I can bring that same joy to those of you reading this.
With that said, I’m going to wrap this one up. The end of the semester is here, and I really should be grading. You can help me out though by continuing to do some reading:
- The Difference Between str() and repr() in Python: A Design by Contract Perspective
- Rock Paper Scissors Using Modular Arithmetic
- Students Should Be Able to Build a Portfolio From Their Coursework
Likewise, here are some helpful Python resources (#ad):
- Effective Python: 90 Specific Ways to Write Better Python
- Python Tricks: A Buffet of Awesome Python Features
- Python Programming: An Introduction to Computer Science
Finally, here’s my list of ways you can help grow the site. Otherwise, have a good day or night! See you next time.
Recent Posts
As the semester starts to wrap up, I'm a bit busy and a bit burnt out. As a result, I thought I'd have a little fun writing about nasty little bugs I've run into over time. I'll keep it short; don't...
I find the structure of relational databases to be appealing. They allow you to store data in various tables that eliminate redundancy, reduce storage size, and combine easily. Therefore, it should...