Suppose that instead of swapping element \(A\)[\(i\)] with a random element from the subarray \(A\)[\(i\) .. \(n\)], we swapped it with a random element from anywhere in the array:
$$\textsc{Permute-With-All}(A)$$$$\begin{aligned} 1& \quad n\,=\,A.length \\ 2& \quad \textbf{for }\,i\,=\,1\textbf{ to }\,n \\ 3& \quad \qquad \text{swap}\,A[i]\,\text{with}\,A[\textsc{Random}(1, \, n)] \\ \end{aligned}$$Does this code produce a uniform random permutation? Why or why not?
No, this code does not produce a uniform random permutation. While it may seem like giving each position more freedom would maintain uniformity, it actually creates a non-uniform distribution.
The algorithm makes \(n\) independent random choices, each from \(n\) possibilities. This gives \(n^n\) total execution paths. However, there are only \(n!\) possible permutations of the array.
For a uniform distribution, each permutation should appear with probability \(1/n!\). This would require each permutation to be produced by exactly \(n^n / n!\) execution paths. But this ratio is not generally an integer.
For example, when \(n = 3\):
- Total paths: \(3^3 = 27\)
- Total permutations: \(3! = 6\)
- Ratio: \(27/6 = 4.5\)
Since \(4.5\) is not an integer, it’s impossible for each permutation to occur with equal probability. Some permutations must be more likely than others.
Analyzing the specific case where \(A = \langle 1, 2, 3 \rangle\) makes the non-uniformity more concrete.
Consider the permutation \(\langle 1, 2, 3 \rangle\) (the identity). This occurs when:
- At \(i = 1\): we swap \(A\)[1] with any position, getting element 1, 2, or 3 in position 1
- At \(i = 2\): we need to get element 2 in position 2
- At \(i = 3\): we need to get element 3 in position 3
If element 1 stays in position 1 initially (probability \(1/3\)), then we need positions 2 and 3 to maintain elements 2 and 3. This happens with probability \((1/3) \times (1/3) \times (1/3) = 1/27\).
But there are other paths that lead to \(\langle 1, 2, 3 \rangle\). For instance, element 2 might move to position 1, then back to position 2, and so on. Counting all such paths is complex, but we can demonstrate non-uniformity by comparing probabilities.
For \(n = 2\), the analysis is clearer. There are \(2^2 = 4\) execution paths and \(2! = 2\) permutations.
Starting with \(A = \langle 1, 2 \rangle\):
Paths leading to \(\langle 1, 2 \rangle\):
- Swap with position 1, swap with position 1: \(\langle 1, 2 \rangle \to \langle 1, 2 \rangle \to \langle 1, 2 \rangle\)
- Swap with position 2, swap with position 2: \(\langle 1, 2 \rangle \to \langle 2, 1 \rangle \to \langle 1, 2 \rangle\)
Probability: \(2/4 = 1/2\)
Paths leading to \(\langle 2, 1 \rangle\):
- Swap with position 1, swap with position 2: \(\langle 1, 2 \rangle \to \langle 1, 2 \rangle \to \langle 2, 1 \rangle\)
- Swap with position 2, swap with position 1: \(\langle 1, 2 \rangle \to \langle 2, 1 \rangle \to \langle 2, 1 \rangle\)
Probability: \(2/4 = 1/2\)
For \(n = 2\), the distribution happens to be uniform (\(1/2 = 1/2!\)). However, this is a special case that doesn’t generalize to larger \(n\).
The original \(\textsc{Randomize-In-Place}\) works because it makes exactly \(n\) choices from decreasing ranges: choice \(i\) selects from \(n - i + 1\) options. This gives \(n \times (n-1) \times \cdots \times 1 = n!\) paths, matching the number of permutations exactly. Each permutation corresponds to exactly one execution path, ensuring uniformity.