Playlist shuffle algorithm

Question

Playlist shuffle algorithm

So this isn't really a request for help, per se, but I'm hoping someone's come across it at some point.

Does anyone know what the iPod's algorithm is for shuffling, at least a playlist? I know the old discussion of "playing favorites" has been discussed to death, but I've observed an odd seeming trend...not only will it play the same artists, but it'll keep coming back to a single album. And it's not that it does this once, or likes a given album. I've been playing through all my music to rate all the songs (so I play the unrated music), and fairly frequently, I'll find it playing multiple songs (3, 4, 5, haven't counted exact numbers) from one album within a small number of tracks. So it'll play something like A, B, C, A, D, A, E, F, G, H, A... (where those are albums).

I know that this can (and will) happen on random plays, and maybe I'm just remember the times it does happen. But it's also crossed my mind that the algorithm for shuffling could very well involve choosing a psuedo-random number and advancing that many unplayed tracks in the playlist. If the numbers are somewhat periodic, this could end up looping the list to a certain block of tracks (which I'm assuming here are sorted by album) repeatedly.

Of course, I can accept the possibility that it's just me, too 🙂 I'm just curious what the actual algorithm is, or, if it's patented, what the patent number is. I'm perfectly happy to read through that, too.

iPod Photo 60GB, Thinkpad T40, iTunes 6.0, Windows XP Pro, Please mark questions as answered when they are. Thanks!

Posted on Dec 22, 2005 12:21 PM

Reply

Answer 1

Buegie

Level 6

13,331 points

Dec 22, 2005 11:04 PM in response to Jonathan Wildstrom

Jonathan,

Every computer programmer has various random number generators to choose from. We used a canned program within our Stats package to generate a random number for each observation, then we would sort by that number to ‘randomize’ the observations.

I suspect that the iPod is doing something similar. No sense in spending too much energy creating something new or proprietary for such a simple task.

It could also be doing a stratified random sample, pulling proportionally from each album or another attribute, but I doubt it.

My small tests suggest that the iPod is not using the 1st song (or other easily repeatable base) as a 'seed' for the randomization. It may be using the time (as many computer programs do). That will eliminate the possibility of easily recreating the same 'random' sort order.

My observations indicate that the algorithm creates a randomized total list for the iPod's Playlist. You can manually scroll through the complete Playlist without a repeat (I’ve verified this). However, if you let the iPod Sleep, or exit out to the main menu and re-enter the playlist, the random list of songs to be played will be recreated from the beginning.

This is how most folks get the idea that the shuffle function is not random. They do not realize that the list gets reset every now and then. More so if they are actively manipulating their iPod’s menu.

The shuffle feature is not truly random, as each song is placed on a sequence that will not change once you start playing songs (unless it is reset as I described above). A truly random list would 'randomly' select the next song based on all songs being available - including the ones just played.

Much like a well-shuffled deck of cards, every now and then (actually quite often), you will find some ‘run’ of cards that make a ‘pattern’: same suit, same value, straights, etc. Same thing with music and Artists, Albums, Genre, etc.

Now I've got 'Weird Al' Yankovic's 'Patterns' song running through my head. Gotta go poke out my mind's ear with a flaming stick. 🙂

Reply

Answer 2

Dec 23, 2005 7:00 AM in response to Buegie

Hmm...I think you misunderstood what I was asking (although you touched on it). Let me start by saying that I'm have CS and Math degrees and I'm a professional programmer. Not that I'm offended, but I know that there are both a lot of random number algorithms and the probability and statistics involved in them. Which is why I can't believe I'm actually falling for the "it plays favorites!" idea.

What I was really wondering is how they use the random numbers. I.e., do they use them to perform a swapping algorithm (swap 1 and random, swap 2 random ones)? Do they use a random selection algorithm (select randomly from 1-n and make it #1, compress list, select randomly from 1-(n-1) and make it #2, etc.)? Do they use a random step (which ought to work the same way, but might not if they used a poor random algorithm)? Which algorithm they use and how they seed it it less interesting to me; I'm assuming they're all good programmers and chose a reasonable algorithm and seed.

Oh, and I know the random play will reset each time around, which is why I'm assuming the random seeding is decent. I just found myself curious if anyone knew how they did the actual shuffling; as a coder, I'm trying to decide what I think would be ther fastest and most reasonable. I think the stepping algorithm would be fastest, as it could actually be done relatively on-the-fly (mark songs as played, generate new random number and count forward, ignoring marked songs). Only leaves the issue of how it can skip backwards songs.

Reply