# Exercise 5.3.4

Professor Armstrong suggests the following procedure for generating a uniform random permutation:

`n = A.length let B[1..n] be a new array offset = RANDOM(1, n) for i = 1 to n dest = i + offset if dest > n dest = dest - n B[dest] = A[i] return B`

Show that each element $A[i]$ has a $1/n$ probability of winding up in any particular position in $B$. Then show that Professor Armstrong is mistaken by showing that the resulting permutation is not uniformly random.

Both are trivial.

$A[i]$ will go to $B[j]$ if $j \equiv \text{offset} + i \pmod{n}$. There is $1/n$ probability of that happening.

It does not generate all permutations - it only generates permutations that can be obtained from the initial input by cycling.

BTW, "Armstrong" and "cycling". Nice pun.