文档教程示例工程【免费下载链接】CLRS:notebook:Solutions to Introduction to Algorithms项目地址https://gitcode.com/gh_mirrors/cl/CLRS点击查看免费下载本文以仓库中的 5.3.md 为主体骨架逐题解析《算法导论》第 5.3 节随机算法Randomized Algorithms的 6 道习题从 RANDOMIZE-IN-PLACE 的循环不变量证明到 PERMUTE-WITHOUT-IDENTITY、PERMUTE-WITH-ALL、PERMUTE-BY-CYCLIC 等候选算法的正确性辨析再到 PERMUTE-BY-SORTING 的均匀性与冲突处理。读完本文你将掌握如何判定一个洗牌算法是否产生均匀随机排列的完整方法论计数论证、整除性检验、平移不变性识别、伯努利不等式下界估计并能直接套用到自己实现的随机化算法中。一、背景5.3 节在讲什么第 5.3 节随机算法的核心思想是通过引入随机性让算法的行为尤其是最坏情况不再依赖于特定的输入分布。典型代表是随机化快速排序见 randomized-quicksort.py先用random.randint(p, r)随机选主元并与末尾交换再做分区。而本节的主角是RANDOMIZE-IN-PLACE——一种原地生成均匀随机排列的算法RANDOMIZE-IN-PLACE(A) 1 n A.length 2 for i 1 to n 3 swap A[i] with A[RANDOM(i, n)]它的正确性依赖 Lemma 5.5 的循环不变量循环不变量恰好在第 $i$ 次迭代$1 \le i \le n$开始之前对每个可能的 $i-1$ 元排列子数组 $A[1..i-1]$ 包含该排列的概率都是 $(n-i1)! / n!$。由该不变量可知循环结束时$A[1..n]$ 是 $n!$ 种排列中的任何一种的概率均为 $1/n!$即均匀随机排列。二、习题 5.3-1让循环不变量在非空子数组上成立原题Marceau 教授质疑 Lemma 5.5 的循环不变量在第一次迭代之前是否成立——他认为空子数组包含 0-排列的概率应为 0从而否定了初始不变量。要求重写 RANDOMIZE-IN-PLACE使不变量在首次迭代前作用于非空子数组并修改证明。解析质疑的本质是空数组的 0-排列这一概念在概率上含糊不清。仓库 5.3.md 给出的思路是彻底避开空子数组把第一次交换单独拿出来处理让循环从 $i2$ 开始RANDOMIZE-IN-PLACE(A) 1 n A.length 2 if n 1 3 return 4 else 5 swap A[1] with A[RANDOM(1, n)] 6 for i 2 to n 7 swap A[i] with A[RANDOM(i, n)]证明要点当 $n 1$ 时直接返回唯一排列即均匀排列不变量平凡成立当 $n \ge 2$ 时第一次交换后 $A[1]$ 以 $1/n$ 的概率等于任意元素非空子数组 $A[1..1]$ 满足不变量$i2$ 时每个 1 元排列出现概率为 $1/n$之后进入循环每个 $i$$2 \le i \le n$迭代从 $A[i..n]$ 中均匀随机选取元素填入 $A[i]$与 Lemma 5.5 的归纳论证完全一致且不再触碰空子数组。这样 Marceau 教授就毫无反驳余地了。三、习题 5.3-2PERMUTE-WITHOUT-IDENTITY 为什么失败原题Kelp 教授想生成任意非恒等排列提出PERMUTE-WITHOUT-IDENTITY(A) 1 n A.length 2 for i 1 to n 3 swap A[i] with A[RANDOM(i1, n)]解析这段代码有三个致命问题根本做不到恒等排列identity permutation恰好是让每个元素都不动。而生成任意非恒等排列与生成所有排列除恒等外是不同的要求——该算法甚至无法保证输出一定不是恒等排列也无法覆盖所有非恒等排列。覆盖不全以 5.3.md 给出的反例说明——像 $[1,3,2,\dots]$ 这种仅交换了后两个元素的序列属于非恒等排列但该算法不会产生它。原因在于当 $i n-1$ 时RANDOM(i1, n) RANDOM(n, n)只能取 $n$即最后一次交换总是 $A[n-1] \leftrightarrow A[n]$使 $A[n-1]$ 与 $A[n]$ 必然互换破坏了排列的任意性。随机范围收窄第 $i$ 次迭代只能从 $i1..n$ 中选取$A[i]$ 永远不可能与 $A[i]$ 自身或 $A[1..i-1]$ 中的元素交换可用排列数远小于 $n!$。结论该过程不满足 Kelp 教授的意图。四、习题 5.3-3PERMUTE-WITH-ALL 不是均匀排列整除性论证原题若第 $i$ 次迭代从整个数组$A[1..n]$ 中随机选取元素交换PERMUTE-WITH-ALL(A) 1 n A.length 2 for i 1 to n 3 swap A[i] with A[RANDOM(1, n)]解析不能产生均匀随机排列。理由采用经典的计数 整除性论证5.3.md 的解答每个 $i$ 有 $n$ 种选择$n$ 次迭代共 $n^n$ 种等可能的交换序列若输出均匀则每种排列的概率应为 $1/n!$即 $n^n$ 个序列必须平均分配到 $n!$ 种排列上要求 $n^n$ 能被 $n!$ 整除但 $n^n / n!$ 不是整数例如 $n3$$3^3 27$$3! 6$$27$ 不可被 $6$ 整除因此必然存在某些排列出现概率高于或低于 $1/n!$。更本质地说该算法每个位置都从全数组取随机元素相邻交换之间存在纠缠导致某些排列如元素多次回到原位的路径被过度表示。真正的均匀洗牌必须像 RANDOMIZE-IN-PLACE 那样逐步收窄随机范围。五、习题 5.3-4PERMUTE-BY-CYCLIC 只是平移原题Armstrong 教授提出用循环移位生成排列PERMUTE-BY-CYCLIC(A) 1 n A.length 2 offset ← RANDOM(1, n) 3 for i 1 to n 4 dest ← i offset 5 if dest n 6 then dest ← dest - n 7 B[dest] ← A[i] 8 return B解析先验证题设中的单元素概率对固定的元素 $A[i]$ 与目标位置 $dest$满足 $i offset \equiv dest \pmod{n}$ 的 $offset$ 恰有 1 个而 $offset$ 均匀取自 $1..n$故 $P(A[i]$ 落在 $B$ 的任一位置$) 1/n$。但这不足以保证排列均匀。关键反驳5.3.md 的解答给定 $offset$ 后整个数组只是循环平移——$B$ 完全由 $A$ 与 $offset$ 决定$n$ 个不同的 $offset$ 只产生 $n$ 种不同排列而均匀随机排列要求 $n!$ 种。当 $n \ge 3$ 时 $n! \gg n$绝无均匀性可言。启示单元素落在各位置的概率均为 $1/n$ 是边缘分布均匀与整体排列均匀是两回事——这正是指标随机变量indicator variables分析法的陷阱所在也是面试中常见的洗牌算法考察点。六、习题 5.3-5PERMUTE-BY-SORTING 优先级全唯一的概率下界原题PERMUTE-BY-SORTING 为每个元素独立地从 $1..n^3$ 均匀随机生成优先级 $P[i]$再按优先级排序输出。证明所有优先级互不相同的概率至少为 $1 - 1/n$。证明5.3.md 给出的推导$$ P(\text{所有 } P[i] \text{ 互不相同}) \left(1-\frac{1}{n^3}\right)\left(1-\frac{2}{n^3}\right)\cdots\left(1-\frac{n-1}{n^3}\right) $$第 $k$ 个元素与前 $k-1$ 个冲突的概率不超过 $(k-1)/n^3 \le n/n^3$故$$ P \ge \left(1-\frac{n}{n^3}\right)^n \left(1-\frac{1}{n^2}\right)^n $$再对 $(1-x)^n$ 用伯努利不等式$x 1/n^2$$$ \left(1-\frac{1}{n^2}\right)^n \ge 1 - \frac{n}{n^2} 1 - \frac{1}{n} $$证毕。这个 $1 - 1/n$ 的下界说明取 $1..n^3$ 的优先级空间冲突概率 $\le 1/n$ 可以接受这也是算法导论选用 $n^3$而非 $n$的原因。七、习题 5.3-6优先级冲突时怎么办重掷法原题当两个或多个优先级相同时如何让 PERMUTE-BY-SORTING 仍产生均匀随机排列解析最简洁的策略是拒绝采样 / 重掷rejection sampling。5.3.md 的解答非常直白既然冲突了那就重新产生嘛。实现如下PERMUTE-BY-SORTING-WITH-RETRY(A) 1 repeat 2 for i 1 to n 3 P[i] ← RANDOM(1, n^3) 4 until P[1..n] 中所有优先级互不相同 5 按 P 升序输出 A 中对应元素正确性论证由 5.3-5 知单次生成中优先级全唯一的概率 $\ge 1 - 1/n$重试的期望次数 $\le n/(n-1) \to 1$$n$ 较大时几乎一次成功且条件化在全唯一事件上后每种排列的出现概率均为 $1/n!$均匀性不受影响。在实际工程中Python 的random.shuffle即 Fisher–Yates等价于 RANDOMIZE-IN-PLACE就是更高效的替代方案无需处理冲突。八、仓库源码佐证随机化的工程实现本仓库为上述理论提供了可直接运行的工程实现证据用 RANDOM(0,1) 构造 RANDOM(a,b)myrandom.py 用 $n \lfloor \log_2(b-a) \rfloor 1$ 个独立随机比特拼出 $0..2^n-1$ 的整数超过上界则重掷rejection sampling最终加 $a$ 得到 $[a,b]$ 区间均匀随机数——这正是 5.3 节所有算法依赖的RANDOM(i, n)的底层实现对应 5.1.md 的 5.1-2 习题。随机化快速排序randomized-quicksort.py 中randomized_partition先random.randint(p, r)随机选主元并交换到末尾再调用确定性分区——与 RANDOMIZE-IN-PLACE 从 $A[i..n]$ 均匀随机选取的思想完全同源是 5.3 节随机化思想在排序算法中的直接落地。随机化搜索problem.md 的 Problem 2 给出了 RANDOM-SEARCH带访问标记的随机抽样与 SCRAMBLE-SEARCH先随机排列再确定性线性搜索的完整伪代码与期望分析展示了随机排列在实际算法设计中的两种用法。九、总结判定均匀随机排列的四个检验综合 5.3-15.3-6 六道习题可以提炼出一套可复用的检验清单检验方法对应习题要点计数 整除性5.3-3总选择数 $n^n$ 必须能被 $n!$ 整除否则必不均匀排列空间覆盖5.3-2 / 5.3-4算法实际能生成的排列数是否等于 $n!$平移只有 $n$ 种循环不变量归纳5.3-1每步从剩余未确定位置中均匀选取逐步收窄冲突重掷下界5.3-5 / 5.3-6用伯努利不等式估计重试代价保证均匀性不受损无论你在实现洗牌、抽样还是随机化算法只要套用这套检验尤其是 RANDOMIZE-IN-PLACE 的收窄式交换就能避免 PERMUTE-WITH-ALL、PERMUTE-BY-CYCLIC 这类看似随机实则偏斜的经典错误。赞分享文档教程示例工程【免费下载链接】CLRS:notebook:Solutions to Introduction to Algorithms项目地址https://gitcode.com/gh_mirrors/cl/CLRS点击查看免费下载相关推荐Toy引擎高级渲染技巧PBR管线与自定义着色器实战教程Toy引擎高级渲染技巧PBR管线与自定义着色器实战教程 Toy引擎作为一款轻量级C游戏引擎提供了强大的PBR基于物理的渲染管线和灵活的着色器系统帮深入解析CLRS项目中的随机算法问题深入解析CLRS项目中的随机算法问题 引言为什么随机算法如此重要 在计算机科学领域随机算法Randomized Algorithm正逐渐成为解决复杂问文档教程教育GeoPandas数据采样技术均匀分布和随机点生成算法GeoPandas数据采样技术均匀分布和随机点生成算法 GeoPandas作为Python地理数据处理的核心工具提供了强大的空间数据采样能力。通过内置的均匀数据分析GIS上一篇Narou.rb 进阶配置清单local_setting、global_setting 与每部作品的 setting.ini 关键设置全掌握下一篇Tech Vault DevOps 挑战实战42个真实场景的解决方案创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考