Shuffling along

One of the sets of algorithms that developers tend to learn pretty early on is sorting a set of items. Bubble sort, selection sort, insertion sort, Shellsort, Mergesort, quicksort. Yeah, these days, your fave set of libraries give you all the sorting methods you’d ever use on, say, an array or list (and probably use quicksort internally), so you’d probably never code one from scratch (and, I’d have to say, even I would have trouble doing so without looking it up). But how about shuffling a set of items?

This is something that caught me out a few years ago: shuffling cards. Imagine you have an array with 52 elements containing the names of the cards as a sorted deck. The task? Implement an algorithm that efficiently and randomly shuffles the elements of this array, that is, the cards, in an unbiased way.

Your first thought might be this: for each element in turn, generate a random number from 0 to 51, then swap it with the element at that random position. So for element 0, calculate a random number from 0 to 51 – say that’s 42 – and swap the elements at 0 and 42 with each other. Move on to element 1 and do the same, then element 2, and so on.

  var simpleShuffle = function (a) {
    var currentIndex = 0;
    var temp, randomIndex;

    while (currentIndex < a.length) {
      // Pick a random element
      randomIndex = Math.floor(Math.random() * a.length);

      // And swap it with the current element
      if (randomIndex !== currentIndex) {
        temp = a[currentIndex];
        a[currentIndex] = a[randomIndex];
        a[randomIndex] = temp;
      }

      currentIndex += 1;
    }
  };

At the end you will have an array whose elements are well shuffled. Except…

…it produces way too many permutations of the cards, and even worse, some permutations will appear more often than others. Think about it like this: after one swap, the permutation we get is just one of 52 possible ones. After two swaps, the permutation we get is again one out of a possible 52, so over the two swaps we now have one out of a possible 52² permutations. If you continue, you can see each swap multiplies the number of permutations by 52, so after 52 swaps we will produce a single permutation out of a whopping 52⁵² possibilities. According to my trusty calculator that is 1.7 * 10⁸⁹.

All well and good, but let’s go back to first principles. In a shuffled deck - which is a single permutation of the cards - the probability that the first card in our permutation appears at the first position is 1/52. Given that, the probability that the second card appears at the second position is 1/51 - since we already know where one card is, remember. The probability that the third card appears at the third position is 1/50, and so on. The probability therefore of getting our particular permutation is 1/52!, where 52! means 52 factorial, or 52 * 51 * 50, all the way down to 1. So there are 52! distinct different permutations of a deck of cards, which is – tap tap tap on my trusty calculator – 8.0 * 10⁶⁷, another whopping huge number. But the problem is that 52! does not divide 52⁵² exactly (pretty obvious since 52! has some prime divisors that don’t divide 52) and so some permutations must occur more often than others, making the simple algorithm somewhat biased.

For a laugh, I decided to map out the permutations for three items, A, B, and C. There are six: ABC, ACB, BAC, BCA, CAB, and CBA. If I went through every single possibility for the simple shuffle algorithm described above and starting with ABC, then I’d get ABC 4 times, ACB 5 times, BAC 5 times, BCA 5 times, CAB 4 times, and CBA 4 times, for a total of 3³ or 27 permutations. It’d be like going to a casino in Vegas with your fave die where three of the faces come up 5/27 of the time each and the other three 4/27 of the time. Score!

No, what we must do is shuffle the cards the way we calculated the number of permutations for a deck: randomly select one out of the 52, then randomly select one out of the remaining 51, and then randomly select one out of the remaining 50 and so on.

  var shuffleArray = function (a) {
    var currentIndex = a.length; 
    var temp, randomIndex;

    while (0 !== currentIndex) {
  
      // Pick a remaining element...
      randomIndex = Math.floor(Math.random() * currentIndex);
      currentIndex -= 1;
  
      // And swap it with the current element.
      temp = a[currentIndex];
      a[currentIndex] = a[randomIndex];
      a[randomIndex] = temp;
    }
  };

OK, a pretty simple algorithm this time, but it did point out that sometimes the simple “obvious” solution is not necessarily the best.

(Aside: the image is a photo of a rare set of limited edition playing cards that I got way back in 2012, which were designed and based upon the cards in the Solitaire game in Windows. Hence the pixelation, and the back of the card.)

  Loading links to posts on similar topics...