Professor Kelp decides to write a procedure that produces at random any permutation besides the identity permutation. He proposes the following procedure:

PERMUTE-WITHOUT-IDENTITY(A)

1 n = A.length

2 for i = 1 to n - 1:

3      swap A[i] with A[RANDOM(i + 1, n)]

Does this code do what Professor Kelp intends?

At first glance, this code seems to do what Professor Kelp claims. Unfortunately at a closer look, there are some permutations that this code cannot produce.

Consider the case where \(A.length = 3\). The permutation \(\{3, 2, 1\}\) should be a valid output, but cannot be generated by this code. At the first iteration of the for loop, we swap \(A[1] = 1\) with \(A[3] = 3\) and so our intermediary array is already \(\{3, 2, 1\}\). At this point we cannot terminate and must perform another swap, resulting in the output array \(\{3, 1, 2\}\). Thus, \(\{3, 2, 1\}\) is not produceable by this code.

In fact, any permutation of the form \(\{n, n-1, \dots 1\}\) is not produceable by Professor Kelp’s code. Suppose in the general case we swap \(A[1] = 1\) with \(A[n] = n\). At this point we have an intermediate array of the form \(\{n, \dots, 1\}\). As the for loop progresses, we will reach a point where we are required to swap \(A[n-1]\) with \(A[n]\) thus moving the value \(1\) out of its desired destination of \(A[n]\). We can avoid this eventuality by swapping \(A[1]\) with some value other than \(A[n]\), but then that stops us from producing an output array with \(A[1] = n\). Only when \(n = 2\) is this not the case, because this code trivially always produces the only non-identity permutation of \(\{2, 1\}\).

Thus this code does not quite do what Professor Kelp claims.