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.