算法导论5.3 Exercises 答案
5.3-1
这份代码可以修改成如下：
1 | RANDOMLY-PERMUTE(A, n) |
初始化过后，位于$A[1]$的元素是均匀从$n$个元素中产生的。因此，初始化时从i = 2开始考虑，因为此时我们已经知道，在第$2$次循环进行之前就已经保持了正确性。
5.3-2
不能。
以$A[1]$为例，经历过第一次循环之后，$A’[1]\neq A[1]$必定成立。使用这个算法，由排列$\langle 1,2,4,3\rangle$必定不能生成排列$\langle 1,4,2,3\rangle$。
虽然这个算法不会生成恒等排列，但也无法生成一部分非恒等排列。
5.3-3
不能。
根据这个随机算法，可以发现，最终会均匀生成$n^n$种结果。但是当$n\ge 3$时，$n!\nmid n^n$，也就是说，这$n^n$个均匀生成的结果无法均匀地分配给$n!$个排列。因此这份代码无法做到随机均匀产生排列。
5.3-4
对于一个特定的元素$i$，如果offset是从$1\sim n$中均匀生成的，那么代码第4行的dest是从$i+1,i+2,\dots,i+n-1,i+n$中均匀生成的。经过第6行的操作后，dest是从$i+1,i+2,\dots,n-1,n,1,2,i-1$中均匀生成的，因此$i$出现在$B$的任何位置的概率都是$\dfrac{1}{n}$。
然而，这个算法仅仅是随机均匀生成了恒等排列循环右移$1,2,3,\dots,n$个下标的排列，并非随机均匀产生所有排列。
5.3-5
考虑使用循环不变量证明：在值为$k$的循环完成前，集合$S$是从前$k-1$个元素中均匀取样大小为$k-(n-m+1)$的子集所得到的集合；在值为$k$的循环完成后，集合$S$是从前$k$个元素中均匀取样大小为$k-(n-m)$的子集所得到的集合。
初始化：在值为$n-m+1$的循环开始前，$S$恰好为空集，从$n-m$个元素中均匀取样大小为$0$的子集为空集的概率为$1$，因为大小为$0$的子集恰好只有$1$个，因此是均匀取样的。
保持：在值为$k$的循环开始前，集合$S$是从前$k-1$个元素中均匀取样大小为$k-(n-m+1)$的子集所得到的集合，每个这样的集合产生的概率为$\dbinom{k-1}{k-(n-m+1)}^{-1}$。按照这个算法，在这一次循环中，值$k$被添加到集合$S$的概率为$\dfrac{1+(k-(n-m+1))}{k}=\dfrac{k-(n-m)}{k}$。最终生成一个确切含$k$的大小为$k-(n-m)$的集合的概率为$\dbinom{k-1}{k-(n-m+1)}^{-1}\cdot \dfrac{k-(n-m)}{k}=\dbinom{k}{k-(n-m)}^{-1}$。
如果在这这一次循环中，并不是值$k$被添加到集合$S$，那么由于当前集合大小为$k-(n-m)$，因此有潜在的$k-(n-m)$个大小为$k-(n-m+1)$的集合，以$\dfrac{1}{k}$的概率抽样到了一个不属于集合$S$的数添加到$S$中，从而变成现在的集合$S$。最终生成一个确切不含$k$的大小为$k-(n-m)$的集合的概率为$(k-(n-m))\cdot\dbinom{k-1}{k-(n-m+1)}^{-1}\cdot \dfrac{1}{k}=\dbinom{k}{k-(n-m)}^{-1}$。
也就是说，在值为$k$的循环完成后，集合$S$是从前$k$个元素中均匀取样大小为$k-(n-m)$的子集所得到的集合。
终止：最终程序停止时，集合$S$相当于是从$n$个元素中均匀取样大小为$m$的子集所得到的集合。