Miller Shuffle Algorithm
Introduction: Miller Shuffle Algorithm
A new Shuffle algorithm that does not require a persistent data structure resource or give out premature repeats.
Shuffle algorithms are used for MP3 players, and games which deal out from a deck of cards, or some other set of one of a kind items like Boggle or Wordle does. Also by things like software that dole out practice exercise or test material to a student.
With the case of an MP3 player, or any play-list shuffle, one might and apparently some do (even on big name electronics and streaming services), simply use an operation like songIndex=random(NumOfSongs). This use of a PRNG will give you a good mathematical randomness to what is played. But you will get many premature repetitions of song selection. With a population of 1000 to choose from you will get ~37% repeats out of 1000 plays. From the start of a listening session on average a song will repeat within ~26 songs. The % of repeats is the same regardless of the selection population size.
The accepted goal of a “Shuffle” algorithm is herein defined as providing means to reorder a range of items in a random like manner, where each item is referenced once, and only once, when going through the range (# of items). So for 1-52 (think card deck) you get 52 #s in a pseudo random order, or similarly for a song list of 1000s. Re-shuffling gives a very different mix.
The Fisher-Yates (aka <PERSON>) algorithm has been a solution that fixes this unwanted repetition. 242
The 1000 songs play in a 'random' order without repeating. The issue this algorithm does come with is the added burden of an array in RAM memory of 2 times the maximum number of songs (for up to 65,000 songs 128KB of RAM is needed) being dedicated to shuffled indexes for the duration that access to additional items from the shuffle are desired (so as to not give repeats).
BTW, working RAM is the most scarce and coveted memory resource (over that of non-volatile memory type storage). This is especially true when using a micro-controller like an Arduino. And as for a streaming service, it might have 100 million users each expecting to, on any day, resume playing from their shuffled list where they can step back & forth through the selections. So those shuffled lists must all be maintained. Further there may be a mix of 100 thousand users at a time actively playing. The service would have to pull into RAM & replace as needed the shuffle lists over & over on the fly.
The algorithm I present here (I refer to as the Miller Shuffle algorithm) provides basically the same beneficial functionality, as the FY algorithm, with a comparable level of randomness, but without the need of any array or upfront processing.
Besides the presentation of the Miller Shuffle algorithm source code itself, the remainder of this Instructable will be dedicated to characterizing this new shuffle algorithm as well as comparing and contrasting it with other algorithms used to preform shuffle functions.
Supplies
First and foremost the crux of this Instructable is the software implementing the "Miller Shuffle algorithm". The software is provided here so you can then utilize it in your own personal project.
And here it is:
// --------------------------------------------------------
// the Miller Shuffle Algorithm (aka: MillerShuffleAlgo_a )
// produces a shuffled Index given a base Index, a shuffle ID "seed" and the length of the list being
// indexed. For each inx: 0 to listSize-1, unique indexes are returned in a pseudo "random" order.
// Utilizes minimum resources. As such there is no better choice for a playlist shuffle.
unsigned int MillerShuffleAlgo_a(unsigned int inx, unsigned int shuffleID, unsigned int listSize) {
unsigned int si, r1,r2; // randomizing factors, in combination provide ~million different shuffles
unsigned int p=16183; // arbitrary prime #s must be > listSize
unsigned int p2=6197; // p~=2.618p2 (not critical)
unsigned int maxBin, halfBin, xorFlip, topEven;
// compute reference values for later
maxBin=1;
while ((2*maxBin+1) "<" listSize) maxBin=2*maxBin+1; // !!! 242