Cards Shuffling Problem

A common algorithmic problem of interest is Cards Shuffling Problem, which states that given a deck of cards shuffle it randomly. A naive algorithm for this problem can be written as:

for i <- 0 to cardLen
  r = random (0, cardsLen)
  exchange card[i] <-> card[r]

Assume there are two cards, we can see 4 possible combination of (i,r) namely (0,0), (0,1), (1,0), (1,1) leading to 2^2 outputs. If the two cards are {1,2} then probability of {1,2} after shuffling is 1/2 and of {2,1} is 1/2. Even though this algorithm looks correct, it is logically incorrect.

Actually there is a little bug in the above algorithm because of which it's incorrect. For N cards it generates N^N permutations, where as a card shuffle must generate N! permutations. Also N^N is not divisible by N!, hence a bias. A small change in above code makes it correct:

for i <- 0 to cardLen
  r = random (i, cardsLen)
  exchange card[i] <-> card[r]

Generating r randomly from between i and cardsLen 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.