Why does the following code NOT generate permutations randomly? [duplicate]

This question already has answers here: Closed 11 years ago.

Possible Duplicate:

What distribution do you get from this broken random shuffle?

This is from Skiena's Algorithm De开发者_运维百科sign Manual.

Assume that myrand(a, b) generates a random number between a and b inclusive.

The following code generates permutations uniformly at random

for(int i = 0; i < n; i++)
    swap( a[i], a[myrand(i, n-1)]);

whereas the following doesn't.

for(int i = 0; i < n; i++)
    swap( a[i], a[myrand(0, n-1)]);

The question is, why?

---

In the first case there are exactly n! possible paths for execution of the function (first rand has n possibilities, the second has n-1 ...). Since each of the n! possible permutations correspojnds to exactly one of these, they are uniformly distributed.

In the second case, there are n^n possible paths of distribution (n possible chioces the first time, n the second...). This does not map uniformly to the permutations so the distribution is uneven.

To check it out "by hand", generate all possibilities for a small n, like 3

numbers chosen  generated permutation
(0,0,0)         (2,0,1)
...              ...