In the following pseudocode, assume that for any pair of integers $x \leq y$, the function random ( $\mathrm{x}, \mathrm{y})$ produces an integer uniformly chosen from the set $\{x, x+1, \ldots, y\}$.
n=9
for (i=1 to n){
A[i]=i
}
for (i=1 to n){
r= random (i, n)
temp =A[i]
A [i]= A [r]
A[r]=temp
print A[i]
}
Which of the following statements is TRUE of the output of the code?
- It outputs all permutations of $123456789$ with equal probability.
- It never outputs $123456789$.
- It outputs all cyclic permutations of $123456789$ with equal probability, and does not print any other output.
- The output is always $987654321$.
- The output may not be a permutation of $123456789$.
