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!