5.3-1 Marceau教授对引理5.5证明过程中使用的循环不变式表示异议。他对在第1次迭代之前循环不变式是否为真提出质疑。他得理由是人们可以容易地宣城空数组不包含0排列。因此空数组包含0排列的概率应该是0.所以在第1次迭代之前循环不变式无效。请改写过程RANDOMIZE-IN-PLACE，使其相关的循环不变式在第1次迭代之前对非空数组扔适用，并为你的过程修改引理5.5的证明。
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)]
初始化 考虑正好在第1次循环迭代之前的情况，此时i=2.由循环不变式可知，对每个可能的0排列，子数组A[1..1]包含这个1排列的概率是(n-2+1)!/n!=1/n.子数组A[1..1]是一个非空子数组，并且1排列中有1个元素A[1]。因而，A[1..1]包含1排列的概率是1/n。在第1次循环迭代以前循环不变式成立，保持和终止同原文。
5.3-2 Kelp教授决定写一个过程来随机产生除恒等排列外的任意排列。他提出了如下过程。
PERMUTE-WITHOUT-IDENTITY(A)
n=A.length
for i=1 to n-1
swap A[i]with A[RANDOM(i+1,n)]
在进行第i次迭代时，元素A[i]是从元素A[i+1]到A[n]中随机选取的。少选取了A[i]这1个元素，而在每次RANDOM时都少选取一个元素，所以必然少了一部分元素进行排列，也就是说少了一些排列方式不能包含所有排列方式。所以肯定就不能包含任意排列。
5.3-3假设我们不是将元素A[i]与子数组A[i..n]中的一个随机元素交换，而是将它与数组任何位置上
的随机元素交换：
PERMUTE-WITH-ALL(A)
n=A.length
for i=1 to n
swap A[i]with A[RANDOM(1,n)]
这段代码会产生一个均匀随机排列吗？为什么会或为什么不会？
A[i]从A[RANDOM(1,n)]中选择方式有n种，则for i=1 to n有n^n种方式排列。而对于n个数的全排列有n!,(n^n/n!)表示每种元素平均出现次数，可以看出n=1,2时是整数，从n=3开始(n^n/n!)次数不是整数，也就证明了对于某些n 每种元素平均出现次数并不平均。所以答案是否定的。
5.3-4 Armstrong教授建议用下面过程来产生一个均匀随机排列。
PERMUTE-BY-CYCLIC(A)
n=A.length
let B[1..n]be a new array
offset=RANDOM(1,n)
for i=1 to n
dest=i+offset
if dest>n
dest=dest-n
B[dest]=A[i]
return B
请说明每个元素A[i]出现在B中任何特定位置的概率是1/n.然后通过说明排列结果不是均匀随机排列，表明Armstrong教授错了。
从这个代码看出随机函数是在for i=1 to n循环外产生的，所以一旦随机到一个数，那么把其带入到循环里就是固定不变的数了。那么产生offset=RANDOM(1,n)有n种选择方式，一种方式对应于一个固定的1到n的循环，所以只有n种排列方式，因为产生均匀排列需要n!个排列方式n!>n，所以排列方式远远少于均匀随机排列需要的排列方式。
因为对于每个B[dest]的下标dest是等可能(1/n概率)的出现1到n中的数，从A[1]到A[n]有等概率(1/n)赋值给B[1]到B[n]中的每个数。
5.3-5 证明：在过程PERMUTE-BY-SORTING的数组P中，所有元素都唯一的概率至少是1-1/n.P(n^3,n) (P代表对于n^3个数的n排列。),有(n^3)^n个排列方式，所以所有元素唯一的概率是P(n^3,n)/(n^3)^n=(n^3-0)(n^3-1)...(n^3-(n-1))/n^(3n)>=(1-1/n^2)^n根据C.4所给二项式公式：设x=-1/n^2,y=1 (1-1/n^2)^n>=1-1/n (展开二项式前2项便知)得证！
5.3-6 请解释如何实现算法PERMUTE-BY-SORTING，以处理两个或更多优先级相同的情形。也就是说
即使有两个或更多优先级相同，你的算法也应该产生一个均匀随机排列。
那么我们可以做一个循环，只要与前面任何一个数相同，那么当前数就进行随机选数，一直到各个数都不相同为止。