Suppose that instead of swapping element \(A[i]\) with a random element from the subarray \(A[i \dots n]\), we swapped it with a random element from anywhere in the array:

PERUMTE-WITH-ALL(A)

1 n = A.length

2 for i = 1 to n:

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

Does this code produce a uniform random permutation? Why or why not?

This code does not produce a uniform random permutation.

Unlike the code in Exercise 5.3-2, this code can actually produce all random permutations. The trouble comes from the uniform production requirement. Consider the case when \(n = 3\). We would expect all 6 possible permutations to be equally likely. Within the for loop we are exchanging \(A[i]\) with one of 3 different possible values, meaning there are \(3^3 = 27\) possible non-distinct outputs each with a \(\frac{1}{27}\) chance of ocurring. No matter how the possibilities are distributed, it is not possible to form a \(\frac{1}{6}\) chance by repeatedly summing \(\frac{1}{27}\) and so the production cannot be uniform.