Generating permutation

I just read in Skiena's book that it is possible to generate a random permutation with uniform distribution like this:

for i=1 to n do a[i]=n
for i=1 to n-1 do swap( a[i], a[Random(i, n)])

where Random(i, n) generates a uniform random integer in {i, ..., n}

Wow, that's surprisingly simple.
Obviously, the amount of randomness needed is correct:
n * (n-1) * ... * 2. But why the result is uniform isn't clear.

(the next day)
Maybe it is not so surprising at all:
I seem to temember from Lenstra's algebra classes that any permutation can be described as a sequence of n-1 swaps between 1 and an arbitrary element, 2 and an arbitrary element, etc. as long as you leave 1, 2 etc alone from then n. You probably prove this by recursion. The result then follows.


I love Skiena's book with a wealth of interesting algorithms;
I think I'm gonna buy it. See his site:
http://www.cs.sunysb.edu/~algorith/info/form.shtml
http://www.cs.sunysb.edu/~algorith/

BTW, the nerdiest site on the internet:
http://www.research.att.com/~njas/sequences/