Randomly Shuffling an Array
Contents
What is shuffling?
Today, a user by the name of Nanashiiiima asked in the SuShCodingYT Discord channel:
Does anybody know how to assign every value in a randomized array to a unique integer? In my case, I’m trying to assign the 3 variables in my array with one of three values (I don’t want any of them to be the same).
This is a pretty common problem, especially in video games. One example where this might be useful, both in and out of video games, is to play all of the songs in a playlist in a random order while ensuring the listener hears every song exactly once. This is known as "shuffle" and the algorithm described below is indeed how many old school MP3 players implemented the "shuffle" button.
FisherYates Shuffle algorithm
Pleae note, this shuffle algorithm has a number of variations; some of which are generically labeled under the same name. See the "Additional Reading" section at the end of this post. I will be demonstrating the range biasfree, O(n) "modern algorithm". This implementation is also an inplace shuffle. That is, it modifies the original array rather than making a copy. You could easily modify this code to make a copy if you prefer to keep the original array immutable.
First, let's shuffle a simple array of contiguous integer values. This is a good test case because it's easy to visually verify that it's working correctly.


This program prints both the original array and the shuffled array:


Shuffling anything (indexed lookup)
So we can shuffle lists of integers, that's cool, but what if we wanted to shuffle something else? One idea is we may want to randomly name eight NPCs from a list of preprogrammed names. We obviously don't want two NPCs to end up with the same name, that would be confusing! Another idea is a tasty treat chooser. Choosing which treat to grab from the fridge is always tough, so for this example we'll be shuffling an array of tasty treats.
One way to do this would be to use the shuffled array of numbers we generated above as lookup indices into the treats
array. This would us to shuffle many times without modifying the original array.
Here is an example of this approach:


The output if this program is very similiar, except that we now have a shuffle array of tasty treats!


Shuffling anything (inplace)
While there are times when the solution given above for shuffling tasty treat names is useful, there are other times when you may be asking "Why do I need this intermediate array of indices? Why can't I just shuffle the strings themselves?" and of course the answer is: You can! In this last example, I will show you how you can use this method to shuffle arbitrary data inplace.
This is the same algorithm as above, which runs in O(n), but you should consider the cost of the copies for the numerous swaps that have to occur in order to shuffle an array inplace. For an integer (above) or a string pointer (below), the cost is trivial, but for a more complex data types and larger arrays, the cost of performing O(n) copies to and from the "tmp" variable to perform the swaps may become more noticeable or even prohibitive. This is unlikely for most reasonable usecases, but good to keep in mind.
Alright, so now let's do an inplace swap of tasty treats!


This program outputs a shuffled array of tasty treats:


Additional reading
The FisherYates Shuffle Wikipedia article has a great overview of the history of this algorithm. It also dives deeper into common mistakes and possible sources of bias. The algorithm I've described above is the one described as the "modern algorithm" in the Wiki article. Assuming I've implemented it correctly, this variation elimnates shuffle bias due to range errors, but does not attempt to eliminate modulo bias or PRNG (pseudorandom number generator, i.e. rand()
) bias. Read the Wiki article for more information on these topics.
Closing remarks
The FisherYates Shuffle is a fast and efficient way to randomly shuffle a collection while ensuring no additional duplication or repetition, aside from any that is already in the original list. Hopefully this post has you thinking of new and creative ways to add variation to your game, or any other software project!
Happy coding!
Thirdparty links
If you'd like to check out the SuShCodingYT Discord server, you can join it via this link:
https://discordapp.com/invite/xtthkcF
This Discord server is the community hub for Suraj Sharma's YouTube channel, which you can find here:
https://www.youtube.com/channel/UC2i39AOpDSlO1Mrn1jQ8Xkg