5.3 Randomized algorithms

5.3-1

We can randomly swap the first element first, then start the for loop from the second element.

RANDOMIZE-IN-PLACE(A)
n = A.length
swap A[1] with A[RANDOM(1, n)]
for i = 2 to n
    swap A[i] with A[RANDOM(i, n)]

And here is the initialization step: before the first loop iteration, i = 2. The loop invariant says that for each possible 1-permutation, the subarray A[1..1] contains this 1-permutation with probability (n - i + 1)!/n! = (n - 1)!/n! = 1/n. The subarray A[1..1] contains only one element, contains 1-permutation with probability 1/n, so the loop invariant holds prior to the first iteration.

The maintenance and termination steps remain the same.

5.3-2

No, it cannot get any permutation, for example, the identity permutation.

5.3-3

This method can produce $n^n$ permutations, but there are only at most n! permutations. So some permutations have duplicates. If each permutation has same number of duplicates, which means $n^n$ is divisible by n!, then the code can produce a uniform random permutation, otherwise, it can not.

Let's consider n - 1, it's obvious that n - 1 is a divisor of n!. Then lt's prove n - 1 is not a divisor of $n^n$ for n > 2.

To make it simple, let's compare $(n + 1)^{n + 1}$ and n for n > 1. We can write $(n + 1)^{n + 1}$ as $a_{n + 1}n^{n + 1} + a_nn^n + \ldots + a_1n + 1$. Thus $\frac{(n + 1)^{n + 1}}{n} = a_{n + 1}n^n + a_nn^{n - 1} + \ldots + a_1 + \frac{1}{n}$, which is not an integer when n > 1. So $(n + 1)^{n + 1}$ is not divisible by n when n > 1, thus, $n^n$ is not divisible by n - 1 when n > 2.

So $n^n$ is not divisible by n!, otherwise, n - 1 must also be a divisor of $n^n$. Thus, the code cannot produce a uniform random permutation.

5.3-4

The code shifts each element in A by k positions by cyclic, k ranges from 1 to n, thus each element A[i] has a $\frac{1}{n}$ probability of winding up in any particular position in B.

This is not a uniformly random because it cannot generate all possible permutations, it can only generate n permutations.

5.3-5

There are $(n^3)^n$ permutations, and there are $A_{n^3}^{n}$ permutations that all elements are unique. Thus, the probability that all elements are unique is:

$$ \begin{eqnarray} P &=& \frac{A_{n^3}^{n}}{(n^3)^n} \\ &=& \frac{n^3(n^3 - 1)(n^3 - 2)\ldots(n^3 - (n - 1))}{(n^3)^n} \\ &=& 1\frac{n^3 - 1}{n^3}\frac{n^3 - 2}{n^3}\ldots\frac{n^3 - (n - 1)}{n^3} \\ &=& (1 - \frac{1}{n^3})(1 - \frac{2}{n^3})\ldots(1 - \frac{n - 1}{n^3}) \\ &\geq& (1 - \frac{n}{n^3})(1 - \frac{n}{n^3})\ldots(1 - \frac{n}{n^3}) \\ &=& (1 - \frac{n}{n^3})^{n - 1} \\ &=& (1 - \frac{1}{n^2})^{n - 1} \\ &=& 1 + (n - 1)(-\frac{1}{n^2}) + \frac{(n - 1)(n - 2)}{2}(-\frac{1}{n^2})^2 + \frac{(n - 1)(n - 2)(n - 3)}{3!}(-\frac{1}{n^2})^3 + \ldots \\ &=& 1 - \frac{n - 1}{n^2} + O(\frac{1}{n^2}) - O(\frac{1}{n^3}) + \ldots \\ &>& 1 - \frac{n - 1}{n^2} \\ &>& 1 - \frac{n}{n^2} \\ &=& 1 - \frac{1}{n} \end{eqnarray} $$

5.3-6

Regenerate the priorities array, until all elements are unique.

5.3-7