Puzzles, Maths and Algorithms: Cards Shuffling Problem

Puzzles, Maths and Algorithms: Cards Shuffling Problem

Cards Shuffling Problem

A common algorithm problem is Cards Shuffling Problem, which states "how to shuffle a deck of cards randomly" or in more general "how to randomize an array of elements". A naive algorithm for this problem can be:

for i = 0 to N    r = random (0, N)    exchange C[i] and C[r]  

Assume N=2. We see 4 possible combination of (i,r) namely (0,0), (0,1), (1,0), (1,1), leading to 2^2 outputs (N^N in general). However, card shuffling should only lead to N! permutations. So even though this algorithm looks correct, it is logically incorrect. A small change in the above code makes it correct:

for i = 0 to N    r = random (i, N)    exchange C[i] and C[r]  

Generating r randomly from between i and N ensures that once a card is swapped to a given i, it's position is fixed. Above algorithm, with iteration on cards in reverse order is Knuth-Fisher-Yates shuffle algorithm.

Read full article from Puzzles, Maths and Algorithms: Cards Shuffling Problem