oddsblogs

A while back, I was writing a blackjack simulator where I needed to model shuffling a deck of cards (randomizing the elements of an array). This problem seemed simple; so simple that I made a big mistake. The code I was writing was in Java, but the examples here are in C.

The simple, logical approach to randomizing arrays is to loop through the array, and swap each element with some random element. This might look something like below.

Here, swap interchanges two array elements (brilliant, I know).

While this does indeed “mix up” the elements of the array, it doesn’t model true card shuffling. To shuffle a deck of cards, we want to produce one out of all the possible permutations (different arrangements or orderings) of the deck, where each occurs with equal probability. How many different permutations are there of n cards? For the first position, there are n choices, times (n-1) choices for the second, and so on, so n! (n factorial).

So whatever method we use to shuffle the array, we want there to be n! different orderings. Now, back to the piece of code above. For the first position, there are n possibilities (where n=length). For the second position, there are also n possibilities, and the same for every other position. This gives us nⁿ possibilities. This is too many!

Fortunately, this is an easy fix. At each iteration, we want one less possibility to choose from. The for loop counter is handy for this.

I think this is a great example of how simple algorithm analysis can improve code.

Popularity: 58%

Share This