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 / 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.

Tags: , , , ,

33 Responses:

  1. Matt Lee says:

    There’s a new native Music app coming soon, maybe they’ll finally fix it!

    I would just like iTunes to return, personally.

    • jwz says:

      "The app called iTunes was replaced by this new app called Music" is a transparent lie. They just filed the serial numbers off. It even has the same AppleScript bindings and bugs.

      • Along with no CD ripping...and because iTunes did decent CD ripping for so long, there's jack for a decent 3rd party app. I'm now using a command line tool from homebrew (along with ffmpeg for mp3 and a node based ID3 tagger) because none of the UI apps I can find (all going back to 10.5 and before) are 64bit compliant.

        • jwz says:

          Uhhh, I ripped a CD with on macOS 12.1 just yesterday. It's still in there, and the settings look the same as I remember them always looking.

          • I'll check again, but on my new M1 mini, when I stuck in a CD with Music running, nothing happened. I thought I read somewhere last year that when they got rid of iTunes, that cd handling was something they weren't putting in the replacements, so I just presumed that was it.

            "If you don’t see information for the CD, select the CD under Devices in the sidebar." Nothing showed up there.

            • dzm says:

              Works for me.

              13" MBPro, M1 chip
              "Music" version
              macOS version 12.2 beta (21D5025f)

              • Connect DVD/Blue-ray reader to USP port(s)
              • Insert CD
              • Familiar grinding/clunking sounds as head reads disc
              • See disc show up in Music side bar under "Devices" section (Devices was not present until disc was inserted)
              • See "CD Info" and "Import CD" buttons toward upper right corner of "Music" app window

              • "Import CD" preferences in "Music" prefs, but confirmation preference screen appears once "Import CD" is clicked. AAC, AIFF, WAV, MP3, Apple Lossless, etc options are provided. Presets exist along with "Advanced" preferences.

  2. Placeslost says:

    Apple Shuffle… where they play every version of the song in a row somehow.

    • Elusis says:

      Apple shuffle, where my 300-track "BIKE BIKE BIKE" playlist picks the same eight songs 50% of the time.

      • Dude says:

        Apple: "Use our products... or DIE!!!!"

        (Seriously, this is an actual Apple spot that makes that very implication) :

  3. mdhughes says:

    My solution is a bit labor-intensive to set up, but it's perfectly satisfactory for me now.

    Make "GENRE awesome not recent" smart playlists, which select on genre, **** or better (or whatever you use for your ratings), opt-click the ... to get an AND operator, not played in last 30 days, not skipped in last 30 days. Now I can hit shuffle, and it can't play the same song again for a month.

    "Shuffle" just sets a random play order for the entire playlist, with zero logic about spacing out artists or albums, but if you have enough albums in there it doesn't bunch them up too badly.

    Infuriating part: iTunes let you set playlist view, specific columns, and every new playlist inherited from whatever playlist you were on at the time. Now in "Music", they're always reset to some horrible no-information view, and I have to manually cmd-J, songs, check a bunch of fields and drag them around to see my goddamned music data.

  4. jr says:

    It's certain that Apple uses some sophisticated AI and therefore:
    * no one knows how this works
    * it is superior per se
    * no bugs

  5. S4usageD0g says:

    My biggest gripe with the Spotify system is that, probably in a effort to save resources, it only shuffles the first 200 songs on a list.

  6. Jeff Allen says:

    > Dear iTunes team: you are bad at your job and you should feel bad.

    This is jwz gold.

  7. Dave says:

    I don't use Apple but I have Amazon Music Unlimited and in a ~1500 song playlist played on shuffle mode I feel like I see lots of repeats of a few songs. My working theory has been that Amazon is prioritizing tracks for which they play lowest fees to play.

    • jwz says:

      It's hard to go wrong with the base assumption that a corporation will always do the most self-serving, vile thing. Especially when it comes to music industry payola. But it is at least very hard to intuit that when it comes to shuffling, since our minds have funny ideas about what "random" is, and, as demonstrated above, the code is actually a bit tricky.

      • Dave says:

        Definitely... I'd like to see a big ol' log of what I've played at random setting over the last few months, but I don't know of a way to do that.

      • Dave says:

        Definitely true. I'd love to have a log of what I've played over the past n months, and that could probably be used to determine quality of randomness, but don't know of a way to do that.

    • Jon H says:

      The other possibility would be favoring tracks that, in some inscrutable big data way, are associated with the listener buying shit from Amazon.

  8. db48x says:

    I always just prefer to pick a random index and play that track. No need for anything fancy.

  9. Jay says:

    Your approach is similar to how we did it at Grooveshark. It seemed like the only sane option. The only addition is that once something has been played we maintained a historical list so going back obeys the list order and so does playing forward once you have gone back; you don't start getting shuffled songs until you are at the end of that list. And even with repeat on, you won't hear the same song twice until you have already played through everything once.
    It astonishes me how just about everyone gets this wrong.

    • John Doty says:

      It was non-obvious to me, at least, so thank you for that. I know that somehow “sample and reject” always feels like failing, or bad somehow. It always comes as a surprise to me how effective it is.

    • Ian says:

      Well.. it depends, doesn't it?

      My ideal music shuffle let's you say 'I like this track' (and 'I like this track a lot') and plays them suitably more often than the 'I don't like this much but ok' ones in the list.

      It also has a mechanism for saying 'always play this track after that one' so I don't have to join the file for Trans Europa Express to Metall auf Metal and Abzug manually to avoid having the middle of a favourite piece appear by itself, for example.

      I do remember that Apple's original algorithm was said to be completely random, but even Apple customers didn't like that, so it was changed.

      I am now wondering how Rockbox does it enough to look at the source. It doesn't meet my wishes above...

      • thielges says:

        I suspect that some “shuffle” algorithms do take into account how much you like a track and use that info to bias selection to play your likes more often.

        So how does the music app know you like a track aside from explicit stuff like assigning a 5 star rating? There are implicit ways to harvest that info from how you use the UI. If you explicitly select a track then the app might conclude that you like it. Similarly if you fast forward or advance past a track after listening for a few seconds then the app can conclude that you don’t like it.

  10. dzm says:

    I've buit a house of cards involving smart playlists to try to guarantee some level of randomness AND that eventually all the music I own will get played. I'd bore you with details of those smart playlists, but I recognize this isn't actually what you're looking for. You just want to know what clearly broken voodoo they're doing under the hood.

    The only anecdata I can contribute is that on iOS the Shuffle seems to get seed/salt from a USB and/or USB head unit. My wife's vehicle has a ~10 year old (maybe older) head unit in it, and either of our iOS devices connected to it turns to spectacular shit when on Shuffle. As in taking a 2,000 track playlist and playing the same four artists over and over, the same 12 tracks, often multiple times, in less than an hour. Disconnect from that head unit and Shuffle at least picks up some semblance of "random" selection of those 2,000 tracks again. I have found no way to make the head unit stop providing "stupid salt" and just be a goddamn speaker. (Well ... I suppose I could place some bullshit third-party Bluetooth adapter into the AUX jack or something.)

  11. thielges says:

    While traveling through LA’s South Central neighborhood last week, my iPhone on full library shuffle played four gangster rap tracks in a row, which is odd since that genre occupies less than 1% of my library. But instead of chalking that up to some sort of GPS influenced algorithm, I’m going with coincidence. Weirder things have occurred before.

  12. nooj says:

    I've actually thought about this a lot in terms of bricks on buildings. Bricks aren't all the same color, which is good, but I'd expect to see some clustering of colors once in a while. Brick-sided buildings always seem so boring to me up close, because there are never splotches or patterns of color, like you see with grain patterns and colors of wood.

    I guess it's because every pallet of bricks always comes in a balanced shuffle, or because people are too afraid that if buildings have random patterns on them, someone might see a dick shape in the randomness. Oh, the humanity.

    • Adolf Osborne says:

      Bricks are often sorted by people, on-site.

      Sometimes, the sort is to give the appearance not something random while minimizing the occurrence of any patterns that must eventually emerge from True Random.

      And sometimes, the sort is to promote a certain repetitive pattern.

      There's lots of ways to sort bricks.

      (I'd link to an article about it, but the Google is so thoroughly fucking poisoned that finding anything about bricks that doesn't relate to Lego is approaching impossible.)

  13. Jon H says:

    The shuffle algorithm I've wanted (since I used an iBook) would pick a random artist and play 2 or 3 random songs from them, then pick another artist, and so on. (Also with a similar option available of picking a random album and playing a few songs from it.)

    Because I often find that shuffle will throw up a song and I'll want to hear some more like that, but after a couple more songs I'm ready to move on to something significantly different.

  14. Bruce W says:

    Good music scheduling is a lot more complex than most people realize and certainly any techbro could even possibly contemplate. I did it professionally for years. I was going to do something on iTunes, but Apple makes things way more complex than required, so I lost interest and started writing PHP websites instead.

    I have never seen anyone do it right, but try to convince a techbro of anything related to playing music is just an exercise in talking to a wall.

  • Previously