How Spotify's Shuffle Algorithm Works.

Short version: for each artist: take every song by them; randomize their order and assign them a value spread evenly between 0% and 100%; finally, order all songs by that coordinate.

It seems like a reasonable approach. Here's an older, slightly more complex version: Balanced shuffle.

The downside of both of these is that it's a bit memory heavy, and requires sorting the entire set at once, which means that it can't react sensibly to new songs having shown up in the corpus after playback has begun; or to requests un-balancing things.

In jwztv (and prior to that, in Gronk) I used a test-and-retry approach instead: pull a random track from the corpus, and reject it if it doesn't satisfy a set of constraints. Those constraints include things like: don't repeat a track within time N; don't repeat an artist within time M; don't allow the same song to be explicitly requested within time O; etc. It's possible for a corpus to have unsatisfiable constraints, so you have to relax constraints after too many consecutive failures.

Whatever it is that iTunes / Music.app does is A) not either of these, B) terrible, and C) incomprehensible. Seriously, if someone inside Apple can tell me what the hell it is doing, I would love to know just to satisfy my own curiosity, as it seems to be going out of its way to do the stupidest possible thing and it has been driving me batty for at least 16 years.

I assume that "go fix the shuffle algorithm" is now some kind of cruel hazing ritual for each new intern on the iTunes team.

Previously, previously, previously, previously, previously, previously, previously.