Shuffle

A shuffle refers to a random permutation. It is widely used in casinos and online gambling. A shuffle must be unpredictable and produce each of the permutations with equal probability.

In 2010, Microsoft Windows 7 browser ballot was tested. The idea was to prompt the users to install a browser providing a list of five browsers to select from. The order of the browsers had to be completely random. Due to a flaw in the shuffle generation algorithm, the browsers were not listed in a random manner. The IE browser was shown in the last position 50% of the time and the Chrome browser was shown in one of the first three positions most of the time. (http://www.robweir.com/blog/2010/02/microsoft-random-browser-ballot.html)

Considering a deck of cards, there are 52! possible permutations of cards. All these permutations must appear with same probability. To get a perfect shuffle, the Knuth's shuffling algorithm can be used. Here is the outline of this algorithm:

void shuffle(int* cards, int n) { //cards: an initial or previous permutation, n: 52

  for(int i = (n-1); i >= 0; --i) {

    j = a random number between 0 and i

    swap(cards[i], cards[j])

  }

}

The algorithm starts filling the permutation in a reverse order. Consider the last position, i = 51. As no other cards are chosen yet, this position can be filled in 52 possible ways. Once the 51^st card is fixed, the 50^th position can be filled by choosing one of the remaining 51 cards. In this manner, the entire permutation can be filled in 52 * 51 * 50 * … * 1 = 52! ways. The time complexity of this algorithm is O(n).

The random number generator used to generate j is crucial for a generating perfect shuffle. The use of a psuedo random generator for generating j produces a biased permutation.

An alternative to Knuth's shuffle is to perform a sort based shuffling. The 52 cards are assigned numbers at random. The cards are then arranged in the sorted order of these random numbers. Care must be taken care that the random numbers are generated properly and no two cards are assigned the same random number. In cases where the random numbers are duplicated, the sorting algorithm results in a biased permutation. The complexity of this sort based shuffle is O(n logn).

The shuffle concept is not restricted to cards, it can be applied to shuffle a set of numbers as well.