When listening to music, most of us reach for the shuffle button on the regular. This is then followed by a bunch of frustrating skips as we hear the same four or five tracks that have been regularly replayed for the last few days. [Ron Miller] wants to fix unsatisfying shuffles, and he’s developed the Miller Shuffle algorithm to do so.
[Ron] realized that many big name streaming services use incredibly simple algorithms to choose shuffled songs. This can often be as simple as songIndex=random(NumOfSongs). The problem with this is that even with a good random number source, you’ll get a lot of premature repetitions. If your music service doesn’t keep track of your shuffle-point between sessions, you’ll often get annoying repeats if you’re listening on a day-to-day basis.
To fix this, the Miller Shuffle algorithm aims to offer good randomness and no repeats without the excess resource usage of the commonly-cited Fisher-Yates algorithm. [Ron] explains it like this: “The way the algorithm works its magic is by utilizing multiple computations which are ‘symmetrical’, in that the range of values which go in are the same values which come out albeit in a different order.” Since its a deterministic fixed list, there’s no need to keep track of what songs have already been played to avoid repeats. Instead, the player must simply step through the index in order, one track after another. As long as a referenced index point is maintained, along with an ID of the shuffle order being used, no repeats should come up.
If you’re implementing a shuffle algorithm for your own music, you might want to give [Ron’s] work a look. He’s taken into account details like resource usage and small and large list sizes, to account for implementation issues for even very large streaming services. If you’re more interested in shuffling cards than songs, though, we can help there too!
If there is something I do NOT want, it is for my music to shuffle. I am very much an album listener, where I listen to a whole album at a time.
That’s fine, this post then isn’t for you then so feel free to shuffle along.
Sure. But the article talks about “most of us” (i.e. “most of us reach for the shuffle button on the regular”), and really most of us don’t (because it kind of sucks), so I feel dissent and counter opinions are welcome (just as much as if there was incorrect technical information).
That said, some sort “intelligent” shuffle that doesn’t suck would be very welcome.
Eh, there’s a lot of popular things equivalent to shuffling. All FM or internet radio stations are randomized, and you change stations in lieu of shuffling. Youtube mixes / recommendations on autoplay are not album by album, but you press next in lieu of shuffling. Many/most playlists which aren’t “1337 minutes of X artist’s greatest hits” are random too. Some streaming sites let you stream an artist, or that artist’s greatest hits, but still generally make specific albums rarer. The main format that still separates by album is music *purchases*. For a music library composed of such purchases, you generally can set the player you’re using to group by song or by album (or sometimes by file system folder, depending on implementation). Often by artist or sometimes genre too. The shuffle only applies to however it was grouped, unless they did it wrong.
In your case, why is there not a way to just shuffle to play the entire album instead of a certain song? After all, an album is basically a long song anyway. Even better if you could select this easily to just add certain or all folders to be randomized and played as if they were just a playlist. Could even add functionality to rank songs or albums to enhance the likeliness that they will be played.
There is open source software called Strawberry (a derivative of Clementine) that works with Linux and Windows and Mac that presumably would let you do this and if not, someone could write a plugin to do so. Which given this is already open source seems like it would be a fairly quick thing to add and credit Ron with.
Is there no way to simply have this shuffle approach just be a plugin for some halfway decent software? Seems like it would be an improvement.
@Random coin flips cause song repeats! said: “There is open source software called Strawberry (a derivative of Clementine) that works with Linux and Windows and Mac that presumably would let you do this and if not, someone could write a plugin to do so.”
* Strawberry Music Player
https://www.strawberrymusicplayer.org/
Strawberry is a cross-platform music player and music collection organizer. It is aimed at music collectors and audiophiles. With Strawberry you can play and manage your digital music collection, or stream your favorite radios.
* Comparison of free software for audio
https://en.wikipedia.org/wiki/Comparison_of_free_software_for_audio
Agreed. It’s a shame that nothing has ever come close to the Empeg’s usability in this regard. Mine lived on random album shuffle, with one touch skip album or artist for when something came up I wasn’t in the mood for.
There is a difference between picking a random song, and shuffling a list of songs.
When you shuffle, you won’t get repeats by definition. (Cfr: Shuffling a deck of cards.)
My player allows to shuffle albums. so entire albums are plays as intended after each other. (Logitech Media Server)
While I enjoy listening to many Pink Floyd albums from start to finish, I’d also like the variety of (for example) Rick Wakeman’s Journey To The Centre Of The Earth (or just Vivaldi’s Four Seasons), rather than going straight from Wish You Were Here to The Wall.
Shuffling albums is a thing, too.
I’m honestly amazed this hasn’t been solved before. Isn’t this used by something like the shuffle in card games which have deterministic shuffles?
Any Why can’t Spotify just use FY and store the array on my phone? I get that it adds up if it’s on the server but my phone can handle 128k for a shuffle. [Grumpy huff]
Anyway, good work. Very useful.
Now please can we have an EU mandate for all services to implement it in place of their crappy shuffles?
Games have been either implementing some sort of accounting overhead or simply doing repeated tests & retries for collisions; when they didn’t actually use Fisher-Yates or a pre-FY algorithm.
Most issues are old and have been solved.
The problem is that today’s people are quiet dumb and everyone is a developer without any IT (or even general) knowledge.
“Those who cannot remember the past are condemned to repeat it.” – George Santayana
It’s solved for pretty much any local media player I’ve ever used (from desktop software to mobile devices to fixed-function car head units).
It may be a problem for streaming services, but I’ve not found those worth using (track selection outside of pop music too narrow, waste of money with your library evaporating on a whim, lack of availability outside of network signal areas when mobile, lack of flexibility in platform use, etc).
It’s not solved for YT Music. Love hearing the same songs every day or every other day /s
Well, it’s Youtube. A better shuffle algorithm would just be providing the same songs every other day, in a slightly different order. It’s hardly a wide selection pool to start with.
I’ve always wanted a shuffle algorithm that picks a random artist or album and plays two or three random tracks, before picking another artist or album, and so on.
Because sometimes on shuffle mode a song comes up and I want to hear a bit more like that song. But not too much more.
Could also do one of these bunches randomly amidst regular shuffle operation.
Kind of like when a radio station throws in a “double shot” and plays two songs by an artist instead of one, like a treat for the audience.
I’ve always wanted a shuffle that only picks the good songs out of albums and not the filler songs.
With iTunes you can rate each song. I’m guessing this makes the song more likely to come up. You can probably set songs to not play during shuffle or delete these songs. How else is a music player supposed to know which songs you like best?
Quod Libet and Ex Falso and Clementine and Strawberry all run on most major operating systems and let you rank songs too. With Quod Libet, you can even change how it ranks so if you want to rank 1 out of 6 or 1 out of 10, that all works.
I think you can also rank songs a 0 and select things like do not play this song. Unclear how much weight you can actually give them though but presumably someone could come up with a better plugin to make ranking a bit more improved?
No no, it should just know.
But you can identify the general problem: rating songs is too much work and takes forever until the algorithm eventually starts to behave. Relying on other peoples’ rankings means being subjected to music labels who hire people to game the search engines by submitting false rankings.
The fundamental problem is that artists generally get one or two hits, and fill the album with a bunch of duds to justify the asking price. Only few artists can consistently pull off an entire CD without adding fluff.
“No no, it should just know.”
Not sure if it’s still in recent versions, but back when large capacity iPods were A Thing, iTunes had a ‘genius playlist’ function that would monitor which tracks you listened to and which you skipped during shuffle playback (synced between desktop and device(s)) and modify their probability to be surfaced in future shuffles based on that.
Though the algorithm doesn’t know whether I’ve skipped the song because I don’t like it, or because I don’t want to listen to it this time.
It isn’t used for song frequency, but you can make playlists like “3 stars and up”, and just shuffle that playlist.
Random groups of 3 songs…
Me too! And I wrote one back in the early 2000s. Couple lines of python, tied into MPD.
This is the way!
Fisher-Yates doesn’t require “the added burden of an array in RAM memory of 2 times the maximum number of songs”. You can shuffle the input array in-place as described in the wikipedia article: https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle . This is one of the most basic algorithms. The problem of repeats isn’t the algorithm choice, it’s when the algorithm is called. If you randomize before you iterate through the shuffled list, you won’t get repeats. If you randomize the list before (or after) playing each song, you will definitely encounter repeats.
Something very similar once was created for the very old program winamp. Maybe it has been forgotten in time, but not by me. It also had this nifty feature you could indefinately turn back and forward in selected numbers.
It wasn’t a real random, but an ingenious pseudo-random with a seed in settings. I’m still using winamp as of today.
yeah, winamp already solved this loong time ago, nothing play twice in shuffle mode. I even need to add song twice or four time, so i can listen more the song that I like when in shuffle mode
I loved winamps shuffle. It would not repeat a song until the list has run through, you could set a parameter for how “shuffled” you want your playlist. From “as-is” over have roughly the same order but shuffle within the next few songs to complete “random” over all entries.
Is it known whether the algorithm used by winamp was based on Fisher-Yates?
The source was leaked out on a torrent (it is called beos ultimate collection)
Or you could just press randomize on the playlist itself. Then you could look ahead and remove whichever songs you didn’t want, re-order them, or put them in queue for playing out of order and then automatically jump back to the list…
And one of the best features that’s missing in most software is “Stop after current” and “Stop after queue”, which means you don’t have to manually stop the player if you only want to hear these three songs this time out of a large playlist.
Hopefully they don’t erase all those good features in the upcoming new version.
yep, Winamp spoiled me decades ago. Every mp3 player and streaming platform since then has lacked certain feature that Just Worked in Winamp.
Now, how is one to take an existing no-brand mp3 player, somehow decompile its firmware, put this better algorithm in place of the truly awful shuffle one programmed in, recompile, reflash and have ones mp3 player doing this? I’m talking things like supermarket or verbatim/sandisk branded devices. Thanks
Rockbox is an open firmware that began on the iRiver devices but I’m not sure about it’s random shuffle algorithm.
My relation to music is … complicated at the moment. Upto about 6 years ago I used to play mostly albums, but with a private collection of over 10.000 of them, you can shuffle those too. I once wrote a simple python script to select 5 random albums and order MPD to play them in the morning. If you do this, then make sure you have skip button to the next album next to your bed.
Only today I learned that my old CD-player used to use Fischer-Yates or similar when those things still existed. A simple alternative is to use a maximum run length shift register. It must have enough bits of course, and also skip numbers if the output is a bigger number then the amount of songs you have.
But storage is cheap, and it’s negligible to the size of the music itself. Therefore it seems more appropriate to have your software manage a database that keeps track of how often and when each song or album is played. And you can extend such a database with tags of how much you like some albums, create tags for different moods or “other”.
Unfortunately I have never found a good Open Source audio player. I used Clementine for a while, but is was impossible to browse trough 10.000 artwork pictures. If I selected that tab, it took minutes to load (and not cached). I just checked, and the project apparently died in 2016. I find it quiet puzzling that there apparently is not enough overlap between open source software and people who care about their personal music.
Strawberry is a newer version of Clementine. No idea how it handles large databases exactly though is 10,000 albums that huge of a database these days? Quod Libet can be pretty neat but neither it nor Strawberry seem to be lightning fast on cheap but modern hardware.
Is there no way to multicore that or otherwise make it super fast? I can see the initial setting up of things taking some time but if you just want to play something and easily browse, there is definitely room for improvements there.
If anyone has a better idea, would certainly like to know.
Strawberry Music Player is a currently maintained fork of Clementine.
This sounds, to a degree, like the opposite of what you see here?
https://www.youtube.com/watch?v=kPRA0W1kECg
Basically take a linear list of play order and just randomly shuffle it up to determine the play order of the songs? It seems to basically just print out a pseudo random order for the playlist by taking every single song you present it and then generating a list literally in a random way unless I am missing something?
But how do you do things like prioritize replays or clump things together here? Every song has exactly one play and it does not even let you prioritize songs that you really like to play more often in the beginning or spread throughout or certain songs to play together or certain songs to not play at all or not play a random chapter of an audiobook or certain songs to be played first or let you sort it by things like song date, etc.
Is there a way to sort of select these types of desired elements and then generate this pseudorandom fixed list? Sort of a way of adding extra variables before you generate the playlist?
I’d quite like to know what is going on here, and the article and README.md didn’t really let me in on what is special. All psydorandom number generators are cyclic, they have to repeat at less than or equal to the maximum number represented in the state. It’s also easy to generate a https://en.wikipedia.org/wiki/Full_cycle. So all the of the goals can be trivially achieved by using one that is full cycle and then just throwing away any number that is larger than the number of songs you have. The number thrown away can be tiny, not enough to worry about, and can be zero. Is this what is happening here, and if not why isn’t this cited as the basis for doing something smarter? As things stand, all the stated goals can be easily achieved using known algorithms so it would be good to know what the new bit is.
randomise(playlist), enjoy()
Just use an LFSR + a salt + MOD and you’re done. LFSR, if configured correctly, will iterate through all the permutations before repeating. Adding a salt will ensure a different set of numbers. Very simple code. No over engineering needed. Just three lines of code.
Using MOD to reduce the range of returned numbers will cause repeats. e.g. mod 10 will return 0 for LFSR values 10, 20, 30, …
This, but no modulo.
My localized ‘shuffle’ consists of listing all tracks in alphabetical title order and just playing the list. It never repeats until the library is exhausted and it’s random enough to be interesting.
As someone who has long worked at various levels of the music and tech industry.. there are 0 of the services that you listen to that have any intent of actual randomness in their shuffle. Ther intent is to differenlty serve you their choices being served according to metrics of things like chart success, ad network licensing of the labels providing the tracks, etc.
That’s not necessarily true. For example you could be shuffling among the work of an obscure artist with minimal market relevance.
Probably still weighted by some sort of automated market metric.
Oh, a better random. When music services get repetitive on shuffle I assumed it had to do with royalties and the service minimizing cost and maximizing profit. When it comes to playing music files stored locally with a player that truly implements next_index = random(song_count) I never noticed a problem. (unless the collection was too small and no algorithm can fix that)
I thought maybe this was going to be something that analyzes the songs’ sounds and tries to play more similar ones back to back making the genre shifts more gradual so you don’t get that jarring effect of say having a hard rock song followed by a pretty melody or vice versa yet you could still combine them in the same collection and the shift back and forth would happen in more gradual steps.
You get it Twisty Plastic. I’m looking for the same.
I’ve seen some truly horrendous shuffle algorithms in fairly recent mp3 players (I’m thinking of a particular sony thumb drive style one), it basically seeds the psuedorandom function by the position of the selected song and only generates something like 20-25 “random” songs which then loop infinitely. So not only do they loop, but if you start by selecting the same song then the sequence will always be the same. It’s ridiculously bad.
I had a friend of mine that would put his MP3 player on random. When one song ended, he would be able to tell me that the next song would be with a couple guesses. It was real bad.