Kishore Karanam archive  

Shuffling cards the right way!

February 02, 2020.


Lately, because of too much series on LA and vegas, the idea of casino and more specifically the idea of cards and poker became an obsession for me. So, I started playing Zynga poker and a little bit of Texas Hold 'em, and have to say it's one of the most fascinating games ever existed. I mean the idea of playing poker for money seems exciting af but the idea of cards and probability is even more intriguing. So, after watching too many videos on cards and "magicians" shuffling them in an insanely crazy manner I've started to shuffle the cards more and more for fun and that's when I got stuck with an issue and when I googled it, I came across an epic algorithm for shuffling the cards in a right way. So, as always I'm writing on it so that I can understand it more clearly.

The normal shuffle

So, when playing any card game the first thing everyone does is shuffling and mostly everyone shuffles in the same manner I mean even though it can be different in looks the bottom line is the same, they pull a random card from the deck repeatedly and set it aside, incrementally building a new stack. Seems pretty fine huh? well, it is fine as long as you pick each remaining card from the deck with equal probability but it doesn't work that way. Here's where it shits the bed.

The problem with the normal random shuffle is it over shuffles the cards in the deck by selecting each card's swap from the entire deck every time which means that some cards are getting moved multiple times!!! Let's write down the code for this shit and we'll see it more clearly.

Now let's see an example to understand this more precisely. Take ABC as there cards to shuffle the basic iterations will be ABC, BAC, CBA, next iteration it changes as ABC turns into BAC, BAC into ABC, CBA into BCA, slowly as you keep doing this at the end you'll list 27 possible outcomes and if you gather them together it'll be like this…


Here you can see many combinations have been repeated that is if the shuffle was random then each three-letter order would occur the same number of times but you can see that ACB, BAC, and BCA are produced more often. So, this isn't a good way to shuffle as for three cards we saw how it screwed now imagine how much it'll shit the bed if we're trying to shuffle the playing cards which has 52 cards in the deck or else the stupid tarot cards(no offense) which will have 78 cards in a deck… So, for this reason, we use a better shuffle and that is the Fisher-Yates Shuffle Algorithm.

The better Shuffle

The idea is simple af. We pick a random element from the front and place it in a new location in the back. The unshuffled element in the back is swapped to the front where it waits for subsequent shuffling. To put it simply, We iterate through each card starting from the end of the array to first, we look for all positions that have not been shuffled yet. All swaps happen in-place at the end of the array, and once a card has been shuffled into place, it can't move again. Let's write the code for this and we'll see the explanation later.

The code is self-explanatory so let's see a simple af example. Let an array have 5 elements and let those elements be 1,2,3,4,5. So here the current index will be 5 and from range 1–5 let's pick a random number to shuffle and let that number be 2 so on shuffling 2&5 the array becomes 1,5,3,4,2. Now, we move forward by making 4 as the current element, and now the range to pick the next random element is narrowed down to 1–4, and let's pick 3 this time and shuffle with 4 and now the array is 1,5,4,3,2. As we move on with this method the final shuffled array will be 4,5,1,3,2.

So, to conclude Fisher-Yates shuffle is a kickass algorithm to shuffle the deck of cards in a more efficient manner but anyway who gives this much shit while playing cards with friends? no one so fuck it. But this knowing this algorithm feels nice.