算法导论5.3 Exercises 答案

5.3-1

这份代码可以修改成如下：

RANDOMLY-PERMUTE(A, n)
  swap A[1] with A[RANDOM(1, n)]
  for i = 2 to n
    swap A[i] with A[RANDOM(i, 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\)的子集所得到的集合。