Marceau教授不同意下述引理证明中使用的循环不变式。他对第1次迭代之前循环不变式是否为真提出质疑。它的理由是，我们可以很容易宣称一个空数组不包含0排列。因此，一个空的子数组包含一个0排列的概率应该为0，从而第1次迭代之前循环不变式无效。请重写过程RANDOMIZE-PLACE，使得相关循环不变式适用于第1次迭代之前的非空子数组，并为你的过程修改下述引理的证明。
RANDOMIZE-IN-PLACE(A) 1 n=A.length 2 for i=1 to n 3 swap A[i] with A[RANDOM(i,n)]
引理：上述过程课计算出一个均匀随机序列。
证明：
在循环的第i次迭代开始前，对每个可能的(i-1)排列，在A[1…i-1]中出现的概率是(n-i+1)!/n!;
初始化：在循环的第1次迭代开始前，i=2，A[i-1] = A[ 1]，由代码可知，此时A[1 ]中随机的包含A中元素的1排列， 满足循环不变式;
保持：假设在循环的第i次迭代开始前，循环满足不变式，即A中的元素的(i-1)排列，在A[1…i-1]中出现的概率是(n-i+1)!/n!，第i次循环，随机选择A[i…n]中元素的一个1排列赋值到A[i]，那么每个1排列出现在A[i]中的概率是1/(n-i+1)，考察第i次循环结束后序列A[1…i]，由于A[1…i-1]是A中元素的一个i-1排列，A[i]只能从除去这i-1个元素的剩余元素中选择，所以A[1…i]是A中元素的一个i排列，而这个i排列出现在A[1…i]中的概率为A中元素的一个(i-1)排列出现在A[1…i-1]中的概率乘以剩余元素的一个1排列出现的概率，即为(n-i+1)!/n! * 1/(n-i+1)= (n-i)!/n!=(n-((i+1)-1))!/n!，所以在第i+1次迭代开始前，满足循环不变式;
终止：此时，i=n+1，按照不变式A[1…n]中存储着A中元素的一个n排列，而且每个n排列出现的概率为(n-(n+1)+1)!/n!= 1/n!，也就是说过程RANDOMIZE-IN-PALCE生成了均匀随机序列。
初始化：在循环的第1次迭代开始前，i=2，A[i-1] = A[ 1]，由代码可知，此时A[1 ]中随机的包含A中元素的1排列， 满足循环不变式;
保持：假设在循环的第i次迭代开始前，循环满足不变式，即A中的元素的(i-1)排列，在A[1…i-1]中出现的概率是(n-i+1)!/n!，第i次循环，随机选择A[i…n]中元素的一个1排列赋值到A[i]，那么每个1排列出现在A[i]中的概率是1/(n-i+1)，考察第i次循环结束后序列A[1…i]，由于A[1…i-1]是A中元素的一个i-1排列，A[i]只能从除去这i-1个元素的剩余元素中选择，所以A[1…i]是A中元素的一个i排列，而这个i排列出现在A[1…i]中的概率为A中元素的一个(i-1)排列出现在A[1…i-1]中的概率乘以剩余元素的一个1排列出现的概率，即为(n-i+1)!/n! * 1/(n-i+1)= (n-i)!/n!=(n-((i+1)-1))!/n!，所以在第i+1次迭代开始前，满足循环不变式;
终止：此时，i=n+1，按照不变式A[1…n]中存储着A中元素的一个n排列，而且每个n排列出现的概率为(n-(n+1)+1)!/n!= 1/n!，也就是说过程RANDOMIZE-IN-PALCE生成了均匀随机序列。
