So, recently I was writing some code, and I was presented with a problem. I had a List<CustomObject> in C#. I needed to jumble that list up and still use those items. Keeping in mind that I am not one of these prodigies that went to MIT, and I do not memorize algorithms for fun, I set about like most good programmers to Stack Overflow. I came across this post which provided me this code:
The post refers to this as a “Fisher-Yates shuffle.” I couldn’t help but think that it sounded impressive. It’s got a couple of names, looks smart. I also realized that maybe I should analyze this a little more. After all, I modified it so work with my program. I know, those of you who are smart enough are going to look at that code and ask, “Why did you modify this? It’s made to be generic.” Yes, I know, but I wanted to, I wanted to be in full control of the code, plus I was using some modified randomization code. Maybe I’ll write another post about random.
According to an internet search, I found that quite a few people have reviewed this, so I am not an original. In fact, you just might find a better article about this elsewhere. Check out this post; it is very technical and intelligent. However, after doing some further research, I found the Fisher-Yates shuffle on the NIST website. They indicate that this shuffling algorithm was developed by R.A. Fisher and F. Yates in 1938. It works like this:
- Get a list (We’ll call this list A)
- Get the number of items in the list.
- Start counting backward from the number of items in the list.
- Pick a random number from 1 to n (n being the total number of elements in the list A), and we’ll call that number k.
- Put the item from count backward point n into the point k spot, and vice versa.
- Repeat steps 3-5 until list n gets back to 0.
So let’s relate these steps to the code. On line 4 of the code, you see that the function takes a single input. It takes an IList<T>. I am assuming that not everyone is incredibly trained as a programmer, so even this could be a little confusing. What is an IList<T>? IList is a list that inherently has an index. Meaning that you can choose an item by its position in the list. This is useful as we said because we need to know how many items are left in list A. So what is <T>? This is a “generic” object. This means that this function can accept an indexed list of any type of object. So taking the long way to get there, line three is step 1.
Line 6 gets the number of items in the list, which is step 2. Line 7 starts the loop and says that it will run as long as n is greater than one, this is step 3. Line 8 immediately minuses one from variable n.
Line 9 gets a random number inside the list of messages, that is counting down. Now, there are a lot of discussions online about true random numbers, and how to really get them. This solution makes use of the Random() function that .NET provides. In my answer, I made use of another piece of code I found on Stack Overflow here:
Sometime in the future, I’ll have to write an article about random. Just know that I used this instead of what is the solution random number. This is step 4.
Step 5 is the logic portion of the code. This logic is done by lines 10 – 12. Line 10 creates a generic object called value and places what is in the list at the random point in that object. Line 11 takes the item at the countdown point n and puts it in the random spot. Line 12 then makes the object that was put into the variable value in line 10 and puts it at point n on the list. This logic continues until you have counted n down to 1. When you are done, you have all the same items in the list but a different order.
With regards to Big O notation, this algorithm appears to me to be O(n). This notation means that the length of time it takes to complete this algorithm is directly proportional to the number of items in the list. If you increase the number of elements in the list, you increase the time the algorithm takes in a linear fashion.
As I have said, I am not an expert or prodigy. I can still learn, so, if you have any better way to shuffle a list, or if you find anything I said to be incorrect, please let me know. I also am attempting to make sure to give the appropriate recognition where that is due, so if I forgot a reference, please let me know, and I’ll update.
Fisher-Yates shuffle. (2017). Xlinux.nist.gov. Retrieved 28 May 2017, from https://xlinux.nist.gov/dads/HTML/fisherYatesShuffle.html
IList(T) Interface (System.Collections.Generic). (2017). Msdn.microsoft.com. Retrieved 28 May 2017, from https://msdn.microsoft.com/en-us/library/5y536ey6(v=vs.110).aspx
James, M. (2017). How Not To Shuffle – The Knuth Fisher-Yates Algorithm. I-programmer.info. Retrieved 28 May 2017, from http://www.i-programmer.info/programming/theory/2744-how-not-to-shuffle-the-kunth-fisher-yates-algorithm.html
List<T>, R. (2017). Randomize a List<T>. Stackoverflow.com. Retrieved 28 May 2017, from https://stackoverflow.com/questions/273313/randomize-a-listt