《算法导论》习题 5.3.1 - 5.3.7
5.3-5 带星号我抄了一下题目, 5.3-6 比较有意思我抄了一下题目, 其他的题可以自己对照书(原书第三版).
5.3-1
直接考虑第2次循环前, 第1次循环后第1个位置的元素是原集合1 ~ n中任意一个元素的概率总是
1
/
n
1/n
1/n, 所以可以以此为循环不变式的起点而不必使用空集合和0排列。
5.3-2
容易证明该算法一定不会产生恒等排列, 因为第一次循环后第一个元素一定是原排列中2 ~ n中的某个元素。现在证明Kelp教授没有实现均匀随机排列。
其实最简单的证明方法是给出一个n = 3的特例, 即当输入为1,2,3时, 输出为2，3，1（p = 0.5）或3，1，2（p = 0.5）, 2， 1，3出现的概率为0，显然无法产生一个均匀随机排列。但是这里为了锻炼使用循环不变式，还是用它来进行以下代数上的证明。
Kelp教授的意图为, 经过随机排列之后, 任意一个非恒等排列出现的概率均为
1
/
(
n
!
−
1
)
1 / (n! -1 )
1/(n!−1)。
还是尝试使用循环不变式证明。假设第i次循环之后, 对于任意非恒等子排列出现在前 i 位的概率为
1
/
(
A
n
i
−
1
)
1 / (A_n^i -1 )
1/(Ani−1)。如果假设成立, 当迭代到
i
=
n
−
1
i = n - 1
i=n−1时,Kelp教授的目的实现。相反的, 如果存在某一个i导致该假设不成立, 那么即可另n = i + 1, 即至少对于该n, Kelp教授无法实现其目的, 反证得证。
容易观察到, 当第一次循环结束后, 第1个位置是任意非恒等1元素排列概率为
1
/
(
n
−
1
)
1 / (n -1)
1/(n−1), 满足假设。现在证明下一次循环后该假设不成立。
设事件
E
1
E_1
E1表示i次循环后, 对于任意的特定非恒等子排列，该排列的前 i - 1位出现在数列的前 i - 1 位；事件
E
2
E_2
E2表示该特定非恒定子排列的第 i 位出现在数列的第i位置。当当且仅当
E
1
,
E
2
E_1, E_2
E1,E2同时发生的时候该特定顺序的前i位出现在数列的前i位。该事件的概率为
P
(
E
1
⋂
E
2
)
=
P
(
E
2
∣
E
1
)
∗
P
(
E
1
)
P(E_1 \bigcap E_2) = P(E_2 | E_1) * P(E_1)
P(E1⋂E2)=P(E2∣E1)∗P(E1)。事件
E
1
E_1
E1发生 => 特定顺序的第 i 位在数列的 i ~ n位中。 事件
E
2
∣
E
1
E_2 | E_1
E2∣E1发生的概率是
(
n
−
i
)
/
(
n
−
i
+
1
)
∗
1
/
(
n
−
i
)
=
1
/
(
n
−
i
+
1
)
(n - i) / (n - i + 1) * 1 / (n - i) = 1 / (n - i + 1)
(n−i)/(n−i+1)∗1/(n−i)=1/(n−i+1), 显然
1
/
(
n
−
i
+
1
)
∗
1
/
(
A
n
i
−
1
−
1
)
≠
1
/
(
A
n
i
−
1
)
1 / (n - i + 1) * 1 / (A_n^{i - 1} - 1) \ne 1 / (A_n^i - 1)
1/(n−i+1)∗1/(Ani−1−1)=1/(Ani−1)。所以假设无法递推，反证得证。
5.3-3
该代码显然不会产生均匀随机排列, 证明思路和之前的非常类似, 使用循环不变式即可证明, 这里略。
5.3-4
这个题的意思我没有特别明确。容易证明
A
[
i
]
A[i]
A[i]出现在
B
B
B上任何特定位置的概率都是
1
/
n
1/n
1/n, 因为
d
e
s
t
dest
dest取1 ~ n中任何一个数的概率是相同的, 但是该算法的有一个问题是无法保证每次循环不会修改B上已经被赋值的位置, 该算法甚至无法正常工作，亦没有讨论的必要了。
*5.3-5
题目：证明对于元素为1 ~ n的数列，随机给每一个元素生成 1 ~
n
3
n^3
n3整数标号, n个元素每个标号都不同的概率至少是
1
−
1
/
n
1 - 1/n
1−1/n.
设事件
E
i
E_i
Ei为第i个生成的标号与之前所有标号都不同, 那么每个标号都不同的概率就是
P
(
E
)
=
P
(
E
1
⋂
E
2
⋂
E
3
.
.
.
.
.
⋂
E
n
)
即
P
(
E
)
=
P
(
E
1
)
∗
P
(
E
2
∣
E
1
)
∗
P
(
E
3
∣
E
2
⋂
E
3
)
.
.
.
.
∗
P
(
E
n
∣
E
n
−
1
⋂
.
.
.
⋂
E
1
)
;
即
P
(
E
)
=
∏
i
=
1
n
n
3
−
i
+
1
n
3
=
∏
i
=
1
n
−
1
n
3
−
i
n
3
P(E) = P(E_1 \bigcap E_2 \bigcap E_3 ..... \bigcap E_n) \ 即 \\ P(E) = P(E_1) * P(E_2 | E_1) * P(E_3| E_2 \bigcap E_3) .... * P(E_n | E_{n-1} \bigcap ...\bigcap E_1); \ 即\\ P(E) = \prod_{i = 1}^{n}\frac{n^3 - i + 1}{n^3} = \prod_{i=1}^{n-1}\frac{n^3-i}{n^3}
P(E)=P(E1⋂E2⋂E3.....⋂En) 即P(E)=P(E1)∗P(E2∣E1)∗P(E3∣E2⋂E3)....∗P(En∣En−1⋂...⋂E1); 即P(E)=i=1∏nn3n3−i+1=i=1∏n−1n3n3−i
因为对于i >= 1 有
n
3
−
i
>
n
3
−
n
n^3 - i > n^3 - n
n3−i>n3−n, 所以
P
(
E
)
≥
(
n
3
−
n
n
3
)
n
−
1
=
(
n
3
−
n
)
n
−
1
n
3
(
n
−
1
)
P(E) \ge (\frac{n^3 - n}{n^3})^{n-1} = \frac{(n^3-n)^{n-1}}{n^{3(n-1)}}
P(E)≥(n3n3−n)n−1=n3(n−1)(n3−n)n−1
通分
1
−
1
/
n
1 - 1/n
1−1/n 得
1
−
1
/
n
=
n
−
1
n
=
(
n
−
1
)
3
n
3
=
(
n
−
1
)
3
(
n
−
1
)
n
3
(
n
−
1
)
1 - 1/n = \frac{n-1}{n} = \frac{(n-1)^3}{n^3} = \frac{(n-1)^{3(n-1)}}{n^{3(n-1)}}
1−1/n=nn−1=n3(n−1)3=n3(n−1)(n−1)3(n−1)
显然由
n
3
−
n
≥
(
n
−
1
)
3
(
n
>
0
)
n^3 - n \ge (n-1)^3 \ \ \ \bold{(n > 0)}
n3−n≥(n−1)3 (n>0)
可推出
P
(
E
)
≥
1
−
1
/
n
P(E) \ge 1 - 1/n
P(E)≥1−1/n
得证。
5.3-6
原优先级随机排序算法：给1 ~ n的每个输入随机生成1 ~
n
3
n^3
n3 的整数优先级，根据优先级进行排序。的算法没有考虑随机生成的优先级相同的情况, 给出你的修改使得该算法能处理优先级相同的情况。
思考最极端的情况, 即一次随机生成的优先级全部相同。该事件发生的概率是
(
1
n
3
)
n
−
1
(\frac{1}{n^3})^{n-1}
(n31)n−1, 而我们已经知道, 对于每个优先级都不同的情况, 恒等排列的概率和任意排列的概率相同, 为
1
/
n
!
1/n!
1/n!。所以，如果以任意特定的顺序对全部优先级相同的情况进行处理, 都会导致某一个特定排列的概率增加, 所以必须对这种情况作随机化处理, 所以应该使用如下的方式解决该问题：即当出现优先级相同的情况时, 标记优先级相同的元素, 递归调用该算法直至没有优先级相同的元素存在。现简单说明证明该方法生成的排列是均匀的的证明思路。
设对长度为n的数组生成优先级后, 有k个元素优先级重复
k
∈
[
0
,
n
]
k \in [0, n]
k∈[0,n]。显然这个k个元素的每一个排列单独对应了整个数组的 q 个排列，容易证明
q
=
A
n
n
−
k
=
n
!
/
k
!
q = A_n^{n-k} = n! / k!
q=Ann−k=n!/k!。
在已经出现k个元素优先级相同的情况下, 该优先级数列所表达的排列正好是一个特定的排列的事件
E
E
E， 等于事件
E
1
E_1
E1: 优先级不同的n - k 个元素的顺序恰好是该特定顺序中优先级不同元素对应 的顺序, 和事件
E
2
E_2
E2, 优先级相同的k个元素的某个特定顺序是该特定顺寻。E发生正好E1,E2同时发生即
P
(
E
)
=
P
(
E
1
⋂
E
2
)
=
P
(
E
2
∣
E
1
)
∗
P
(
E
1
)
P(E) = P(E_1 \bigcap E_2) = P(E_2|E_1) * P(E_1)
P(E)=P(E1⋂E2)=P(E2∣E1)∗P(E1)。
显然
P
(
E
1
)
=
k
!
/
n
!
P(E_1) = k!/n!
P(E1)=k!/n!, 若要求
P
(
E
)
=
1
/
n
!
P(E) = 1/n!
P(E)=1/n!, 则需要
P
(
E
2
∣
E
1
)
=
1
/
k
!
P(E_2|E_1) = 1/k!
P(E2∣E1)=1/k!, 正好是要求k个相同优先级对应的元素的每种可能的顺序均为
1
/
k
!
1/k!
1/k!, 而递归应用该算法恰好能达成这一目的。
得证。
5.3-7
证明下列算法
Set<Number> randomSample(int m, int n) {
if (m == 0)
return new Set<Number>();
Set<Number> s = randomSample(m - 1, n - 1);
i = random(1, n)
if (s.contains(i)) {
s.add(n)
}else {
s = s.add(i)
}
return s;
}
可以创建集合{1, 2, 3,… ,n} 的一个大小为m的随机样本使得每一个大小为m的子集的概率相同。
证明
还是尝试使用循环不定式来进行证明。严格意义上集合不应该分顺序, 但是算法中random(1, n)和集合元素的自然顺序让我们很方便的将集合看作有序的。集合的前 i 个元素意为 {1, 2, …, i}集合中的元素。
假设对于任意的
i
∈
[
1
,
m
]
i \in [1, m]
i∈[1,m]表示递归返回次序（递归越深i越小）。当第 i 次递归返回前，已经选取出的容量为 i - 1的子集是集合S的前 n - m + i - 1 个元素组成的集合的任意一个容量为 i - 1 的子集的概率相等, 均为
1
/
C
n
−
m
+
i
−
1
i
−
1
1 / C_{n - m + i - 1}^{i-1}
1/Cn−m+i−1i−1。当 i 增加到 m + 1 的时候， 从集合中前n个元素选出的任意一个容量为m的子集的概率为
1
/
C
n
m
1 / C_n^{m}
1/Cnm。
i = 1 时, 空集包含空集的概率为1.当i = 2时，第一个选出的元素是S的前n - m + 1 个元素中的任意一个的概率
P
=
1
/
(
n
−
m
+
1
)
P = 1/(n - m + 1)
P=1/(n−m+1)。满足假设。现在证明第i次递归返回后该假设仍然成立。
设事件
E
E
E表示第 i 次递归返回后，返回的容量为i的子集合是S的前 n - m + i元素构成的集合中的某一个特定组合。该特定组合的前 i - 1 个元素一定均小于 n - m + i， 即一定是前 n - m + i - 1元素构成的集合某个容量为 i - 1的子集。
设
E
1
E_1
E1 包含第 i - 1次递归返回的集合属于该特定集合。
设
E
2
E_2
E2 表示第 i 次递归添加的元素属于该特定集合。
设
E
3
E_3
E3 表示该特定集合最大的元素正好是 n - m + i。
事件
E
E
E 相当于
E
1
,
E
2
E_1, E_2
E1,E2同时发生。
P
(
E
)
=
P
(
E
1
⋂
E
2
)
=
P
(
E
1
∣
E
2
)
P
(
E
2
)
P(E) = P(E_1 \bigcap E_2) = P(E_1 | E_2)P(E_2) \\
P(E)=P(E1⋂E2)=P(E1∣E2)P(E2)
无论
E
3
E_3
E3是否发生, 当
E
2
E_2
E2发生时, 该特定顺序集合第 i 次之 前 添加的元素一定小于
n
−
m
+
i
n - m + i
n−m+i，根据假设, 这些元素构成的集合恰好是 i - 1次递归返回的集合的概率为
1
/
C
n
−
m
+
i
−
1
i
−
1
{1}/{C_{n-m+i-1}^{i-1}}
1/Cn−m+i−1i−1。
P
(
E
1
∣
E
2
E
3
)
=
1
/
C
n
−
m
+
i
−
1
i
−
1
P
(
E
1
∣
E
2
E
3
ˉ
)
=
1
/
C
n
−
m
+
i
−
1
i
−
1
P
(
E
1
∣
E
2
)
=
1
/
C
n
−
m
+
i
−
1
i
−
1
P(E_1|E_2E_3) = 1 / C_{n - m +i - 1}^{i-1} \\ P(E_1|E_2\bar{E_3}) = 1 / C_{n - m +i - 1}^{i-1}\\ P(E_1|E_2) = 1 / C_{n - m +i - 1}^{i-1}\\
P(E1∣E2E3)=1/Cn−m+i−1i−1P(E1∣E2E3ˉ)=1/Cn−m+i−1i−1P(E1∣E2)=1/Cn−m+i−1i−1
根据概率论公理：
P
(
E
2
)
=
P
(
E
2
⋂
E
3
)
+
P
(
E
2
⋂
E
3
ˉ
)
P
(
E
2
)
=
P
(
E
2
∣
E
3
)
P
(
E
3
)
+
P
(
E
2
∣
E
3
ˉ
)
P
E
3
ˉ
P(E_2) = P(E_2 \bigcap E_3) + P(E_2 \bigcap \bar{E_3}) \\ P(E_2) = P(E_2 | E_3)P(E_3) + P(E_2 | \bar{E_3})P{\bar{E_3}} \\
P(E2)=P(E2⋂E3)+P(E2⋂E3ˉ)P(E2)=P(E2∣E3)P(E3)+P(E2∣E3ˉ)PE3ˉ
且根据算法描述, 当
E
3
E_3
E3 发生时，
i
−
1
i - 1
i−1次递归添加的元素正好
n
−
m
+
i
n-m+i
n−m+i 的概率是
i
/
(
n
−
m
+
i
)
i/(n-m+i)
i/(n−m+i) 。
E
3
ˉ
\bar{E_3}
E3ˉ 发生时,
E
2
E_2
E2 发生的概率即任意一个
1
1
1 ~
n
−
m
+
i
n-m+i
n−m+i 的数属于一个由均为
1
1
1 ~
n
−
m
+
i
−
1
n-m+i-1
n−m+i−1 的元素构成的容量为
i
i
i的集合的概率，仍然是
i
/
(
n
−
m
+
i
)
i/(n-m+i)
i/(n−m+i) 。
P
(
E
2
∣
E
3
)
=
(
i
−
1
+
1
)
/
(
n
−
m
+
i
)
=
i
(
n
−
m
+
i
)
P
(
E
2
∣
E
3
ˉ
)
=
i
n
−
m
+
i
P(E_2|E_3) = (i - 1 + 1) / (n - m + i) = \frac{i}{(n - m + i)}\\ P(E_2|\bar{E_3}) = \frac{i}{n-m+i}
P(E2∣E3)=(i−1+1)/(n−m+i)=(n−m+i)iP(E2∣E3ˉ)=n−m+ii
根据组合数学, 显然有:
P
(
E
3
)
=
C
n
−
m
+
i
−
1
i
−
1
/
C
n
−
m
+
i
i
P
(
E
3
ˉ
)
=
C
n
−
m
+
i
−
1
i
/
C
n
−
m
+
i
i
P(E_3) =C_{n-m+i-1}^{i-1}/C_{n-m+i}^{i} \\ P(\bar{E_3}) = C_{n-m+i-1}^{i}/C_{n-m+i}^{i}
P(E3)=Cn−m+i−1i−1/Cn−m+iiP(E3ˉ)=Cn−m+i−1i/Cn−m+ii
但因为
P
(
E
2
∣
E
3
)
=
P
(
E
2
∣
E
3
ˉ
)
P(E_2|E_3) = P(E_2|\bar{E_3})
P(E2∣E3)=P(E2∣E3ˉ)，所以其实不必算出
P
(
E
3
)
P(E_3)
P(E3)的概率即可得
P
(
E
2
)
=
i
/
(
n
−
m
+
i
)
P(E_2) = {i}/{(n-m+i)}
P(E2)=i/(n−m+i)。
所以
P
(
E
)
=
P
(
E
1
∣
E
2
)
P
(
E
2
)
=
1
C
n
−
m
+
i
−
1
i
−
1
(
i
n
−
m
+
i
)
故
P
(
E
)
=
1
C
n
−
m
+
i
i
P(E) = P(E_1|E_2)P(E_2) = \frac{1}{C_{n-m+i-1}^{i-1}}(\frac{i}{n-m+i})\\ 故\\ P(E) = \frac{1}{C_{n-m+i}^{i}}
P(E)=P(E1∣E2)P(E2)=Cn−m+i−1i−11(n−m+ii)故P(E)=Cn−m+ii1
当第 i 次递归返回后，假设仍然成立，得证。
总结
循环不变式赛高。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
