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

PERMUTE-BY-CYCLIC(A)

1 n = A.length

2 let B[1..n] be a new array

3 offset = RANDOM(1, n)

4 for i = 1 to n:

5     dest = i + offset

6     if dest > n:

7         dest = dest - n

8     B[dest] = A[i]

9 return B

Show that each element \(A[i]\) has a \(\frac{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.

PERMUTE-BY-CYCLIC shifts the array \(A\) by whatever offset value is generated. Since each value of offset is equally likely, there is a \(\frac{1}{n}\) chance of each individual value being chosen which directly translates into \(A[i]\) having a \(\frac{1}{n}\) chance of winding up in any particular position in \(B\).

This procedure does not produce a uniform permutation because it can only generate permutations in which the original sequence of values in \(A\) is retained. So if \(A\) is \(\{1, 2, 3\}\) this procedure will only generate three possible outputs: \(\{1, 2, 3\}\), \(\{2, 3, 1\}\) and \(\{3, 1, 2\}\).