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 Knuth) algorithm has been a solution that fixes this unwanted repetition. 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. Furthermore, the Fisher-Yate's dependency on a shuffled array makes it subject to the need of periodic recreation, resulting in session to session repeats, and unintentional re-shuffles resulting in loss of play history. The Miller Shuffle gives completely fresh shuffle indexes having only to keep track of the last logical index and a shuffle ID.
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 which might be used to preform a shuffle function.
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; // !!! the quotes should not be in this line
halfBin=maxBin/2; // limit field effected for great variation
xorFlip=0x5555 & halfBin; // choose 5555 empirically
topEven = listSize - (listSize & 1);
//si = (inx%listSize); // allow an over zealous inx
shuffleID+=(inx/listSize); // & have it effect the mix
r1=shuffleID%1009; // constant value is not super important
r2=((shuffleID%1019)*p2)%listSize; // consecutive shuffleIDs now make more varied shuffles
si=(inx+shuffleID)%listSize;
/**** Heart of the Algorithm *****/
si = ((long)si*p + r1) % listSize; // relatively prime gears turning operation
if (si<=maxBin) {
if (listSize>=128) si = (si & 0xFF99) | ((si&0x60)>>4) | ((si&0x06)<<4); // swap some bits
if (si<=halfBin) si=si ^ xorFlip; // flip some bits operation
}
if (si&1) si=topEven-si; // reverse flow of odd #s
si = ((long)si*p2 + r2) % listSize; // more prime gear turning
return(si); // return 'Shuffled' index
}
Due to a glitch in the Instructables editor there is a "<" that should be without the quotes.
The official source for the algorithm is at: https://github.com/RondeSC/Miller_Shuffle_Algo
(This write-up, albeit very informative, predates the latest & greatly improved 'Miller Shuffle-D and -E' algorithm variants, found in the github repository.)
Additionally . . .
It is also in the file MillerShuffle.ino which is in, the attached, Shuffle_Demo.zip, along with other files to form an Arduino sketch "Shuffle_Demo". And is include here for reference purposes.
The Arduino sketch “ShuffleDemo.ino” Demonstrates and Tests the efficacy of the various shuffle algorithms addressed herein.
To run the Shuffle Demo/tester you'll need:
- the Arduino IDE and
- a mini STEM platform follow the link for details.
- the Shuffle_Demo sketch files, available for download below.
or
- Tinker this online demo (note: TinkerCad needs a Fast! CPU else it is very slow with poor sound. And you'll have to make a copy in order to tinker it such that you can operate it and see the serial monitor or Graph output. sad. )
Using the Shuffle Demo & Tests software
Menu Functions btn1: select btn2 < > btn3 bn4: change Algorithm / stop
1) PlaySongList: Listen to a playlist of "tunes", shuffled by the Miller Shuffle Algo
btn1: pause btn2: Prev. btn3: Next btn4: exit
2) Shuffle_Output: gives indexes and selections of Shuffled list using Current Algo (C.A.). Good for Graph output
3) Randomness_Test: calculates Randomness statistics (and outputs values as HEX) for C.A.
4) Test_Albums: Distribution of adjacent selections & freq. of Albums being played re C.A.
5) cardDeal_Test: find how often players would get a pair of given cards dealt to them, for C.A.
The TinkerCad implementation has reduced print out strings as a work-around for stability issues (? stemming from low stack resources in the web based simulation)
Step 1: The Miller Shuffle Algorithm
The algorithm I present here (I refer to as the Miller Shuffle algorithm) provides basically the same beneficial functionality with a comparable level of randomness, without the need of any array or upfront processing.
Characteristics of the Miller Shuffle algorithm
- does Not require RAM memory for an array (saves 2 * size of the # of indexes, over the FisherYales algorithm)
- No upfront processing. Minimal processing to generate any shuffled index on the fly.
- does Not need a record of past plays in order to go back through selections (like using random() would)
- Not dependent on an available PRNG impementation.
I did extensive testing of randomness to insure sufficient and appropriate random characteristics. Refer to the summary of statistics for randomness in image above. For further details see related spread sheet.
(update May 2023: newer variants of the Miller Shuffle algorithm get significantly better statistical results.)
The randomness test I used was a version of 'ENT', with additional tests (32bit Pi, and a 32bit Golden Ratio calculation) I added some years ago when I was developing encryption software. In testing I used 1 to 10s of Kilo-bytes, where results variations may easily exceed +/- several %. For purposes here that should be fine. To get more stable figures of randomness, data files containing millions of bytes are commonly used.
Note that algorithms suitable for use as a shuffle will have all byte values in even quantity (when data set size is a multiple of 256) and due to that … empathy=8.0, 8bit ChiSq=0 and mean=127.5 ((255+0)/2). The other measures are driven by various numbers of multiple bytes and so are sensitive to the random distribution of the byte values.
Step 2: Regarding the Use of Random() and a Simple Shuffle Algorithm
For reference I included ENT statistics from using random(), which should not be used for any of the applications addressed herein, as well as a simple shuffle algorithm. Note that random()’s mean value is not 127.5 (255/2) that is because it will not provide all the possible values of a byte (or for any value range) within a period equal to that range (thus premature repeats).
The simple shuffle (using only a couple of primes & modulus) does a good job of cycling through all the values, but there will be patterns in the selection (perhaps not readily noticed by a user/player). The related statistics for randomness are also weak compared to the FYA.
This weakness can be well visualized in the plot monitor running on an Arduino in the Arduino IDE, when exercising the ShuffleDemo software's 'Shuffle_Output' (menu item #2) (see above image capture). This weakness could, in an MP3 application, reveal itself in songs being taken from a limited number of albums cyclically for a period of time. Statistically this was tested for via ‘Test_Albums’ (menu item #4) by quantifying the distribution of adjacently selected albums and the # of selections between items from the same 'album'. The Simple Shuffle algo got a ChiSq of ~11369(worst of all, best is ~38.3) on the adjacent album distribution, due to the nature of its cyclic patterns. On the "Average extent of early album repeats" test it got 1.5 (best <50) which means it would be the best at not repeating an album within a short time. This is also due to its cyclic nature. Imagine you simply play one song from each of the albums and then cycled back to play a different one in each, you would score a 0 (lower the # less album repetition) on this test, but you would lack a sense of randomness. People are good at seeing (or hearing) patterns even when the math of randomness (ENT) produces measures that don't give a strong clear indication that something is askew.
Test_Albums() as well as PlaySongList(), and Shuffle_Output() emulates an MP3 player configuration of 52 albums (reflected by words starting with a-z & A-Z) of 10 “songs” entries each.
Menu item #4 Test_Albums() check of adjacent selections within albums & frequency of an Album being played
Algo: random()
adjacent values ChiSq: 10 (expected 38.3)
avg extent of early album repeats 46 (best <40)
Algo: SimpleShuffle
adjacent values ChiSq: 11369 (expected 38.3)
avg extent early album repeats 1.5 (best <40)
Algo: Knuth (Fisher-Yates)
adjacent values ChiSq: 12 (expected 38.3)
avg extent of early album repeats 43 (best <40)
Algo: Miller-A
adjacent values ChiSq: 43 (expected 38.3)
avg extent of early album repeats 30 (best <40)
Algo: Miller-B
adjacent values ChiSq is 84 (expected 38.3)
avg extent of early album repeats 43 (best <40)
The ChiSq adjacent values for random() and F-Y are lower than natural. Their ChiSq numbers will look natural with small data samples but with larger & larger data sets (here ~2000) the rand() algorithm unnaturally balances out the distribution of values. The other algorithms result in about the same ChiSq regardless of sample size.
Notice that 'extent of early' for the use of rand(), instead of an actual shuffle algorithm, is the highest (1.5 * Miller-A). I expected it to be much higher given rand()'s untemper tendency to give premature repeats of values. Perhaps the test I device is not well enough suited to sufficiently reflect this behavior.
The only potential effect (reflected in these numbers) that may be noticed is that with a Miller algorithm Shuffle you will a little less readily have album repeats and that you'll jump around more amongst more albums over a given period of time. For the most part, in practice, I would not expect this to be too significant.
Step 3: Observations and Thoughts Regarding the Miller Shuffle Algorithm
The simple shuffle algorithm simply does a couple operations of modulo math with the use of a prime number. The Miller shuffle algorithm adds operations to the interim mapped values of bit shuffling, bit flipping and directional re-sequencing, using 2 boolean operations and one arithmetic. Unlike other shuffle algorithms it does not utilize a PRNG, instead it is itself a sort of new animal, a PRIG (Pseudo Random Index Generator).
These three added operations are symmetrical, in and of themselves, in that all the #s of a range go in and then all come out, but at different points.
This improves the effective 'randomness' and resolves the issues the simple algo had with the 'Test_Albums' results for adjacent distribution and separation of albums. I recommend you also examine the ENT test results above and the graphed values coming out of the Shuffle_Output().
I have added some statistics calculations (comparable to those of ENT.exe) to the Shuffle_Demo Randomness_Test(). Initially it only output raw data I had to feed ENT.exe with to measure randomness. With it you can see that the Miller Shuffle algorithms score in the same range as does random() or Fisher-Yates with a 0.5 - 2.0 average % error.
You can run the Shuffle_Demo software (at TinkerCad) and see the statistic and graphs, like above, being generated.
So Miller Algo-a resolves all of the issues with the simple shuffle algorithm, and for an MP3 application, as well as many others, MA-a is certainly great … and more than simply a suitable replacement for the use of the ‘FisherYates’ algo.
Step 4: Observations and Thoughts Regarding Card Pattern Distribution & Miller Shuffle Algo_B
Pattern re-occurance distribution is tested for by ‘cardDeal_Test’ (menu item 5). The frequency of re-occurrence of a pre-determine specific pair of items is tabulated.
It emulates 26,000 card deck shuffles each time dealing to 10 players, looking for certain card combinations, within their hands. That's over 260,000 examinations, which should find ~100 occurrences across the 10 players, for any given pair of cards.
Menu item #5 cardDeal_Test() check how often a set of players will get two select cards dealt to them.
Algo: R 9 8 8 9 11 6 3 16 12 10
Total: 92 (avg s.be 100)
Algo: S 0 0 0 0 0 0 84 0 76 0
Total: 160 (avg s.be 100)
Algo: FY 14 8 16 15 6 14 9 9 11 10
Total: 112 (avg s.be 100)
Algo: Ma 2 8 0 0 11 19 0 17 11 0
Total: 68 (avg s.be 100)
Algo: Mb 11 16 8 13 12 8 8 9 13 9
Total: 107 (avg s.be 100)
This test shows 'simpleShuffle' to be the worst, but the Miller Algo-a is not looking nearly as good as the FYA. For use with an MP3 player or the selection of exercise or test material MA-a works very well, with more randomity than is needed. But, if one was concerned with the statistical occurrence of say a particular pair of cards from a 'shuffled' deck there is room for improvement there. To rectify this, I devised the Miller Algo-b. I can only see where this could be considered to be needed is where money is involved, like a casino gaming machine. And even then I don't think it would make a significant difference, but there would be a basis to argue this.
Characteristics of the Miller Shuffle algorithm B
- does Not require RAM memory for an array (2 * size of the # of indexes, like FYA)
- Any given combinations occur as Expected over a period of time.
- If there is a functional need to back track history, a record would need to be kept. (Diagnostic recreation is though possible by way of re-seeding the system pseudo random generator and replaying from the beginning of a session.)
In order to address the poor pattern distribution Miller Algo-b goes beyond -a in the following ways. It adds a touch of the random() effect. It randomly returns one of two calculated values, in response to each input index. Its limited use of random() is necessary so as to not require significant bookkeeping in order to continue to be sure that all possible values are returned by the time one steps through all the possible input indexes (viewed another way, only having unique values returned before reshuffling).
Note the improved outputs (MA-b over MA-a) of cardDeal_Test(), as well as in results from ENT. The adventurist may find it interesting to compare the outputs of MA-a & MA-b utilizing the same shuffle-Cut, list-Size and input indexes. This added complexity (found in Miller Algo-b) is really only warranted when an even distribution, over a long period of time, of sets of responses is highly desired (eg: dealing cards to multiple players for money).
Step 5: Additional Attributes to Be Aware Of
Regarding prime-modulo math algorithms (Simple, Algo-a & Algo-b):
The maximum size for the selection pool (listSize) needs to be less than the smallest prime number used in the algorithm. This is so they can not share a common factor (including themselves).
The Miller Shuffle Algorithm’s use of boolean, modulo and arithmetic math shuffling operations can take many forms but each logical transformation needs to output the listSize number of unique values for given the range of input values 0-(listSize-1).
The ENT statistics vary to a degree with the use of different prime numbers, as do they for the size of the number of items (listSize). Also note that the size of the test data given to the ENT.exe is a factor, and especially if the test data size is not a multiple of 256, giving sufficient chance for all byte values to occur.
Changing computational fine details, In the Miller Shuffle Algorithms A & B, may improve a given statistic, it also likely lowers another. It is hard to know (or Guesstimate) which are the better trade offs to make. Also note that you could do only one or two of these added operations and get good to very good results for your application, if for instance you needed or desired to reduce the computations. With any of these minor changes you would still basically have the Miller Shuffle Algorithms A or B; and enjoy the basic functionality and benefits as listed for them.
Step 6: Special Cases
One possible use case: Suppose you only wanted 100 unique items out of 10,000. You could with rand() loop for 100 but you would have to check for uniqueness at least ~5,000 times (100*50) plus retries.
With Fisher-Yates you still need an array of 10,000, which needs to be looped through for initialization, besides doing the loop of 100 to determine the items.
With the Miller Shuffle you can add a parameter as to how many items you want and it would loop that many times and could return an array of just that many items (in our case 100). If you preferred you could loop calling a standard Miller_Shuffle 100 times to get the items, or simply call it as you need them.
There are edge case applications which want for more randomness and some cases are better suited for less.
The case for more, & especially where long term pattern distribution is important is addressed by the Miller Shuffle Algo-B. Like in multi-player card games, where you need a fair distribution of the desired cards among the players.
An example of a case for less even distribution would be doing a Morse Code examination test, where you want a pseudo random selection from all of 26 letters across 50 doled out. random() does too many repeats (of 2,3, 4 & more times) and yet leaves out some letters. The others, shuffle algorithms, will provide an instance of each of the letters once out of each group of 26 given. So when you've been given 20 or so, you may know 2 or 3 of the upcoming, yet to be seen. This is also not desirable in an exercise or test setting. This could be addressed with a modified Miller Shuffle, I call Double Deck Shuffle. Which greatly reduces predictability and significantly reduces the likelihood of a duplicate (which is appropriate, after all there are words like ‘BOOK’, but not ‘GEEEK’)
Typical generated characters for Morse code testing
using random()
AJQJO ZNECH TELKG OBHHN KNHRC
GUBRN MFKVX NVHXL ALLHX ODBRH
using DDeckShuffle()
ERVIA NXMEP BISLB UWHFQ YLTOC
HXKCT VKGPZ GUNDS YJZOW JDQAF
The DDS is simply a Miller Shuffle-A which uses 2* listSize items, shuffles them up then doles out from results. Like with 2 real decks of cards it provides 2 cards of each kind across twice a single deck’s size (104) of deals. In the case of dealing out the first 52, it will give repeats of ½ as many cards as would random() and no triplets or quadruplets of any cards.
The DDS algorithm will test as more random than other Miller Shuffles due to drawing from a redundant set of items resulting in more possible combinations and distributions. But it will not have:.. empathy=8.0, 8bit ChiSq=0 and mean=127.5 as needed for a “good” shuffle algorithm.
Please post regarding any projects you put a Miller-Shuffle algorithm to use in.
Step 7: Response to Request - How It Works
I have been asked to provide more information about the science behind the operations of the algorithm.
Both a PRNG (Pseudo Random Number Generator) and the Miller Shuffle algorithm (which I would call a PRIG, Pseudo Random Index Generator) use a specialized jumble of mathematics to accomplish their ends. Fortunately we don’t need to understand how the pseudo magic is done for it to work for us.
That said I will shed as much light on the mathematic principles at work within the Miller Shuffle algorithm as I can, fairly succinctly.
The Miller Shuffle Algorithm uses boolean, modulo and arithmetic math shuffling operations. It utilizes a few sets of operations each of which is symmetrical, in that across a range of input values an instance of each will at some point be outputted, but in a different order. As an example, for a range of 0-9 consider these operations, where ‘inx’ in a reference index going from 0 to limit-1 (with limit=10) and ‘si’ is a shuffled index
si = limit-inx; // produces: 9,8,7,6,5,4,3,2,1,0
si = (inx+17) mod limit; // produces: 7,8,9,0,1,2,3,4,5,6
si = (inx*17+5) mod limit; // : 2,9,6,3,0,7,4,1,8,5
In particular, in the heart of the algorithm there are five lines of code which change the Shuffle Index ‘si’ (with si=...). The first and the last reorder all the values within the list size range 0 to n-1. For every unique value (0-(n-1)) that goes in, a different yet still unique value comes out. This is done by the like of SI_out=(SI_in*PN + k) mod n.
The prime number (PN) and n have to be relatively prime (share no divisor other than 1). Why this works is explained by the proven theorems of modular math involving primes and their corollaries, which I am not going to begin to explain here. I have provided links to help you get an idea about the nature of this mathematics.
https://en.wikipedia.org/wiki/Multiplicative_group_of_integers_modulo_n
https://www.cs.cornell.edu/courses/cs280/2004fa/280wk5.pdf
https://trans4mind.com/personal_development/mathematics/numberTheory/modularArithmetic.htm
I did not find a reference which was generally understandable and specific to this use case. But I can describe a use case that is a corollary to this one and is easy to understand.
For a gear which engages another gear or chain to wear evenly the number of teeth (sprockets or links) in them has to be relatively prime. So the number on one for instance can not divide evenly into the number on the other. If for instance a large gear had 3 times as many teeth as a gear it engaged, the teeth on the smaller one would each only line up with 3 locations on the other. This would cause cyclic uneven wear. When the number of teeth are relatively prime any one tooth hits a different spot on the other until it gets back to the first spot.
Try it yourself. Mark down say 8 boxes on a paper then step through them with a count of 5, wrapping around as needed (that’s where the modulo plays a part), marking off spots as you go. You’ll see how you hit every spot once and only once before you start over. It works the other way around too, with 5 boxes taking 8 steps at a time. Try it again with 10 and 4 and see what happens (note both #s are divisible by 2).
The prime-modulo operations produce a sort of moire pattern to the numbers. The addition of the constant (k) just moves to a different reference point within the pattern.
The other three lines shuffling the number sequence are mathematically more straight forward. Yet they do so in three different ways. These operations and their interactions amplify the resulting random nature of the final sequence quite significantly. One moves bits and one inverts some bits. These two operations operate within bit boundaries to ensure symmetry and the range of output values. The third arithmetically reverses the flow of odd numbers throughout the sequence.
The idea with ‘r1’ & ‘r2’ is that of randomizing factors, based on the ‘shuffleID’, with values ~0-1000 to give, in combination, theoretically up to a million different shuffles.
The implementation and order of these operations have been optimized through exhaustive testing.
Supporting the shuffling of a larger number of items.
The number of items that can be shuffled is limited by the smallest prime number used in the shuffle algorithm. If you are interested in extending this limit while ensuring not to break the algorithm read the README.md document at
https://github.com/RondeSC/Miller_Shuffle_Algo
