Professor Kelp decides to write a procedure that produces at random any permutation besides the identity permutation. He proposes the following procedure:
$$\textsc{Permute-Without-Identity}(A)$$$$\begin{aligned} 1& \quad n\,=\,A.length \\ 2& \quad \textbf{for }\,i\,=\,1\textbf{ to }\,n-1 \\ 3& \quad \qquad \text{swap}\,A[i]\,\text{with}\,A[\textsc{Random}(i+1, \, n)] \\ \end{aligned}$$Does this code do what Professor Kelp intends?
No, this code does not do what Professor Kelp intends. While it never produces the identity permutation, it does not produce all non-identity permutations with equal probability.
The algorithm never produces the identity permutation because at each step \(i\), we swap \(A\)[\(i\)] with an element strictly to its right (from positions \(i + 1\) through \(n\)). This means element \(A\)[\(i\)] is never left in its original position \(i\). Since every element must move from its starting position, the identity permutation is impossible.
However, the algorithm does not uniformly distribute probability among the remaining \((n! - 1)\) non-identity permutations. To see why, consider a small example with \(n = 3\) and array \(A = \langle 1, 2, 3 \rangle\).
The algorithm makes two random choices:
- At \(i = 1\): swap \(A\)[1] with either \(A\)[2] or \(A\)[3]\((probability\)1/2$$ each)
- At \(i = 2\): swap \(A\)[2] with \(A\)[3]$$ (deterministic, probability 1)
This gives us \(2 \times 1 = 2\) possible execution paths, but there are \(3! - 1 = 5\) non-identity permutations:
\[\langle 2, 1, 3 \rangle, \langle 2, 3, 1 \rangle, \langle 3, 1, 2 \rangle, \langle 3, 2, 1 \rangle, \langle 1, 3, 2 \rangle\]Since there are only 2 execution paths but 5 possible outcomes, the algorithm cannot produce all non-identity permutations with equal probability. Some permutations must be produced more frequently than others (or not at all).
Tracing through the execution paths makes this concrete:
Path 1 (swap with position 2, then swap positions 2 and 3):
- Start: \(\langle 1, 2, 3 \rangle\)
- After \(i = 1\): \(\langle 2, 1, 3 \rangle\)
- After \(i = 2\): \(\langle 2, 3, 1 \rangle\)
Path 2 (swap with position 3, then swap positions 2 and 3):
- Start: \(\langle 1, 2, 3 \rangle\)
- After \(i = 1\): \(\langle 3, 2, 1 \rangle\)
- After \(i = 2\): \(\langle 3, 1, 2 \rangle\)
The algorithm produces only \(\langle 2, 3, 1 \rangle\) and \(\langle 3, 1, 2 \rangle\), each with probability \(1/2\). The other three non-identity permutations are never generated!
The complete picture for \(n = 3\):
| Permutation | Produced by Algorithm? | Probability |
|---|---|---|
| \(\langle 2, 3, 1 \rangle\) | ✓ (Path 1) | \(1/2\) |
| \(\langle 3, 1, 2 \rangle\) | ✓ (Path 2) | \(1/2\) |
| \(\langle 2, 1, 3 \rangle\) | ✗ | \(0\) |
| \(\langle 3, 2, 1 \rangle\) | ✗ | \(0\) |
| \(\langle 1, 3, 2 \rangle\) | ✗ | \(0\) |
To uniformly generate a non-identity permutation, we could:
- Use \(\textsc{Randomize-In-Place}\) to generate a uniform random permutation
- If it’s the identity permutation, generate another one (expected number of trials: \(n! / (n! - 1) \approx 1.0003\) for large \(n\))
Alternatively, use a rejection-free method based on derangements (permutations where no element remains in its original position), though this is more complex.