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 51st
card is fixed, the 50th 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.
