Professor Marceau objects to the loop invariant used in the proof of Lemma 5.5. He questions whether it is true prior to the first iteration. His reasoning is that one could just as easily declare that an empty subarray contains no 0-permutations. Therefore, the probability that an empty subarray contains a 0-permutation should be 0, thus invalidating the loop invariant prior to the first iteration. Rewrite the procedure RANDOMIZE-IN-PLACE so that its associated loop invariant applies to a nonempty subarray prior to the first iteration, and modify the proof of Lemma 5.5 for your procedure.
We can redefine the algo in a very simple way that we do not have to deal with 0-permutation of n array at all and then leave no iota of doubt for professor Marceau.
RANDOMIZE-IN-PLACE(A)
n = A.legth
if n == 1
return
else
swap A[1] with RANDOM(1, n)
for i = 2 to n
swap A[i] with RANDOM(i, n)And now we can use the same loop invarient that was used earlier.
Professor Kelp decides to write a procedure that will produce at random any permutation besides the identity permutation. He proposes the following procedure:
PERMUTE-WITHOUT-IDENTITY(A)
1 n ← length[A]
2 for i ← 1 to n
3 do swap A[i] ↔ A[RANDOM(i + 1, n)]Does this code do what Professor Kelp intends?
没有，因为[1,3,2...]这样的序列虽然不是identity permutation但是却不会产生.
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: 
PERMUTE-WITH-ALL(A)
1 n ← length[A]
2 for i ← 1 to n
3 do swap A[i] ↔ A[RANDOM(1, n)]Does this code produce a uniform random permutation? Why or why not?
不可以，因为本来有n!种排列，但是这种做法每个迭代有n种选择，所以有n^n种选择.而n^n不能被n!整除，因此不是uniform的排列.
Professor Armstrong suggests the following procedure for generating a uniform random permutation:
PERMUTE-BY-CYCLIC(A)
1 n ← length[A]
2 offset ← RANDOM(1, n)
3 for i <- i to n
4 do dest <- i + offset
5 if dest > n
6 then dest <- dest-n
7 B[dest] -< A[i]
8 return BShow that each element A[i] has a 1/n probability of winding up in any particular position in B. Then show that Professor Armstrong is mistaken by showing that the resulting permutation is not uniformly random.
这个算法对于给定的offset,只会产生一种排列...也就是最后只有n种排列而不是n!种. 只会将原数组平移，谈不上随机.
Prove that in the array P in procedure PERMUTE-BY-SORTING, the probability that all elements are unique is at least 1 - 1/n.
Explain how to implement the algorithm PERMUTE-BY-SORTING to handle the case in which two or more priorities are identical. That is, your algorithm should produce a uniform random permutation, even if two or more priorities are identical.
既然冲突了，那就重新产生嘛...
Follow @louis1992 on github to help finish this task.