Card shuffling problem

An intuitive way of doing card shuffling:
starting with a deck of 52 cards,
randomly choose one from the 52 cards as the first card,
randomly choose one from the left 51 cards as the second card,
...
choose the last one left as the last card.

We can implement this using two arrays or two linked lists. But using array the delete operation is not in constant time, using linked list the access operation (choose the selected node) is not in constant time.

A neat solution is to use one array like this:

for (i := 1; i < 52; i ++) {
  randomly choose a card c in the range [i, 52];
  swap card i and card c;
}

Each card has the same probability (1/52) of being chosen for a position. This is uniform distribution. To see this, besides correlating this algorithm to the intuitive solution at the beginning of this article, you can also think this way: the first card is chosen with the probability 1/52, then second card is chosen with the probability 51/52 * 1/51 = 1/52, ... the i-th card is chosen with the probability 51/52 * 50/51 * 49/50 * ... 1/(52-i+1) = 1/52.

It's easy to see that the number of cards 52 can be replaced with a random n.