A permutation p of the numbers {1, 2, ..., n} is called a derangement if p[i] is not equal to i for ...

---

A permutation p of the numbers {1, 2, ..., n} is called a derangement if p[i] is not equal to i for all i. For example, p = [2, 3, 1] is a derangement but q = [2, 1, 3] is not, since q[3] = 3. (Permutations here are arrays indexed as p[1..n].) (a) Give an O(n) expected-time algorithm to compute a uniform random derangement of {1, 2, ..., n}. Do not give code. (Hint: the number of derangements of {1, 2, ..., n} is the integer closest to n!/e, where e = 2.718... is Euler's constant.) (b) Prove your algorithm is correct. (c) Prove your algorithm has expected running time O(n).