洗牌算法Fisher-Yates Shuffle深度解析从每日一题到等概率排列的实战实现【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode本文是仓库每日一题系列中 2019-07-19 洗牌算法题解 的完整扩展版本。题目要求在O(n)时间内随机打乱一个n元数组并保证所有n!种排列等概率出现每种概率恰为1/n!。读完本文你将掌握经典 Fisher-Yates 洗牌算法的核心思路、JavaScript 实现细节、完整的概率正确性证明以及它与仓库中蓄水池抽样、拒绝采样、三门问题等概率类专题的关联脉络。信息卡片该题解收录于 每日一题汇总 的 2019-07-19 条目属于Array与Probability两个标签的交叉内容时间2019-07-19题目链接暂无tagArrayProbability题目描述假设我们有一个 n 个元素的数组要求你实现一个函数该函数会随机地返回 n 个元素的排列要求所有排列出现的概率是一样的。即每一个排列出现的概率都是 1/n!。对题目做三点解读它们正是本题的验收标准必须随机不能引入任何确定性顺序输出由随机源驱动必须是排列洗牌是原地重排元素集合不变只是顺序改变必须等概率n!种排列每一种被产出的概率都严格等于1/n!这是最容易出错、也最需要证明的一点。朴素思路抽取到新数组的问题最直观的想法是像真实洗牌一样从原数组中随机取出一个元素放入另一个全新的数组不断重复直至取空。这种思路的正确性容易理解——每个元素在每个位置上被取到的概率相同。但它有两个明显的缺陷每次取出都涉及数组删除操作在多数语言的动态数组实现中删除中间元素需要移动后续元素导致总复杂度退化到O(n²)额外开辟了一个等长的新数组空间开销为O(n)。核心思路把取出换成交换原文档给出了一个巧妙的转换把从数组中取出的元素放入原数组的末尾用交换代替删除第 1 次随机取出一个元素时把它与原数组的倒数第 1 个元素交换第 2 次在剩余元素中随机取出时把它与原数组的倒数第 2 个元素交换依次类推第n-1次最后一次无需交换完成洗牌。这样每一轮处理区间都在缩小第i轮只在尚未固定的前缀区间[0, n-i]内做随机选择被选中的元素与区间末元素交换后即被钉死在后缀区后续不再参与随机。整个过程只做了n-1次交换时间复杂度为O(n)空间复杂度为O(1)原地操作仅需一个临时变量。注原文档特别说明第一次交换选择与倒数第 1 个而不是第 1 个交换是因为与末尾元素交换代码更简洁——倒序遍历使得循环边界与随机区间边界天然一致无需额外维护已固定前缀的游标。参考实现JavaScript原题解给出的 JS 代码如下function shuffle(list) { for (let i list.length - 1; i 1; i--) { const random (Math.random() * (i 1)) 0; const temp list[i]; list[i] list[random]; list[random] temp; } }逐行拆解代码作用for (let i list.length - 1; i 1; i--)从最后一个位置开始倒序处理i同时充当当前待固定区间的末尾下标i 1保证最后一轮只剩 1 个元素无需再交换Math.random()返回[0, 1)区间的均匀随机小数Math.random() * (i 1)映射到[0, i1)覆盖区间0..i共i1个整数候选 0位运算取整等价于Math.floor对非负数为截断得到0..i的均匀随机整数三行交换把list[random]与list[i]互换位置i从此固定关键点剖析随机区间每轮收缩第i轮只在[0, i]内取随机下标保证已经固定到后缀的元素绝不会被再次选中这是等概率成立的结构性前提 0与Math.floor的等价性Math.random() * (i 1)的结果为非负浮点数右移 0 位即向下取整可安全使用若读者希望可读性更强也可改写为Math.floor(Math.random() * (i 1))原地修改函数直接修改传入的list无返回值是典型的原地算法in-place。概率正确性证明原文档给出了完整的数学证明这里完整保留并展开推导。第一步任意一个元素放在任意位置的概率均为1/n。放在倒数第 1 个位置的概率第一次随机即在n个元素中选中它概率为1/n放在倒数第 2 个位置的概率第一次没被选中概率(n-1)/n第二次在剩余n-1个元素中被选中概率1/(n-1)两者相乘仍为1/n放在倒数第k个位置的概率为[(n-1)/n] × [(n-2)/(n-1)] × ... × [(n-k1)/(n-k2)] × [1/(n-k1)] 1/n中间的每一项都是上一轮未被选中的条件概率逐项约分后恰为1/n。因此每个元素等概率地落在每一个位置上。第二步所有排列等概率概率为1/n!。洗牌等价于依次确定第 1 位、第 2 位、……、第 n 位的元素。某一种特定排列出现的概率为1/n × 1/(n-1) × ... × 1/2 × 1 1/n!其中第k步是从剩余n-k1个元素中精确选中该排列指定的那一个。这与每一个排列出现的概率都是1/n!的题目要求完全吻合。这与仓库中 蓄水池抽样reservoid sampling 的证明思路同源蓄水池抽样把最终被选中的概率拆成被选中的概率 × 不被替换的概率逐轮约分后所有元素最终概率均为k/n洗牌则把每个位置的概率逐轮约分恒为1/n。二者都是通过逐轮收缩随机区间保证等概率思想的体现。复杂度分析指标数值说明时间复杂度O(n)恰好执行n-1轮每轮一次随机数生成与一次交换空间复杂度O(1)原地交换仅使用常数级临时变量i、random、temp扩展与变体从洗牌到更广的概率算法这道题的价值不只在于一个函数它连接了仓库中多条概率类知识线1. 蓄水池抽样随机抽样 k 个当数据规模大到无法全部载入内存如数据流场景洗牌算法无法直接使用。蓄水池抽样 用大小为k的蓄水池边遍历边替换保证每个元素被最终选中的概率都是k/n。当k n时蓄水池抽样退化为一次完整洗牌两者算法骨架一致。2. 拒绝采样用 Rand7 实现 Rand10洗牌对随机源的均匀性要求极高。仓库中的 470. 用 Rand7() 实现 Rand10 展示了如何用两次rand7()生成7 × 7 49个等概率结果再从中等概率选出 10 个并拒绝其余采样如行号列号法取idx 40再取模保证输出均匀——这与洗牌算法从均匀分布出发构造等概率结构的思维一脉相承也提醒我们当随机源不够均匀或范围不匹配时需要显式的构造或拒绝策略。3. 概率问题的实验验证仓库的每日一题系列中有多次以实验验证概率结论的先例。例如 三门问题题解 附带的 三门问题模拟程序通过Math.random()驱动 100 万次模拟验证换门胜率 2/3这一违反直觉的结论。洗牌算法同样可以照此思路用大样本模拟验证每种排列频率趋近1/n!或验证每个元素出现在每个位置上的频率趋近1/n。4. 栈混洗stack shuffle仓库 基础数据结构英文版 提到合法的栈混洗操作与合法的括号匹配表达式一一对应n个元素的栈混洗种类数恰等于n对括号的合法表达式数量即卡特兰数。注意这与本文的随机洗牌是不同概念——栈混洗只允许通过入栈/出栈重排讨论的是能产生多少种排列而非如何等概率产生排列二者可对照学习。总结算法本质Fisher-Yates 洗牌通过每轮收缩随机区间 原地交换把抽取操作改为交换操作将时间复杂度从朴素的O(n²)优化到O(n)空间复杂度降为O(1)正确性依据逐轮约分证明每个元素落在任意位置的概率均为1/n进而每种排列出现概率为1/n!严格满足题目要求实现要点倒序遍历、随机区间[0, i]每轮收缩、 0取整、与末尾元素交换保持代码简洁知识延伸与 蓄水池抽样、Rand7 实现 Rand10拒绝采样、三门问题概率实验验证共同构成仓库中一条完整的概率算法学习路径建议结合原文与相关题解对比阅读、动手验证。【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
洗牌算法Fisher-Yates Shuffle深度解析从每日一题到等概率排列的实战实现【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode本文是仓库每日一题系列中 2019-07-19 洗牌算法题解 的完整扩展版本。题目要求在O(n)时间内随机打乱一个n元数组并保证所有n!种排列等概率出现每种概率恰为1/n!。读完本文你将掌握经典 Fisher-Yates 洗牌算法的核心思路、JavaScript 实现细节、完整的概率正确性证明以及它与仓库中蓄水池抽样、拒绝采样、三门问题等概率类专题的关联脉络。信息卡片该题解收录于 每日一题汇总 的 2019-07-19 条目属于Array与Probability两个标签的交叉内容时间2019-07-19题目链接暂无tagArrayProbability题目描述假设我们有一个 n 个元素的数组要求你实现一个函数该函数会随机地返回 n 个元素的排列要求所有排列出现的概率是一样的。即每一个排列出现的概率都是 1/n!。对题目做三点解读它们正是本题的验收标准必须随机不能引入任何确定性顺序输出由随机源驱动必须是排列洗牌是原地重排元素集合不变只是顺序改变必须等概率n!种排列每一种被产出的概率都严格等于1/n!这是最容易出错、也最需要证明的一点。朴素思路抽取到新数组的问题最直观的想法是像真实洗牌一样从原数组中随机取出一个元素放入另一个全新的数组不断重复直至取空。这种思路的正确性容易理解——每个元素在每个位置上被取到的概率相同。但它有两个明显的缺陷每次取出都涉及数组删除操作在多数语言的动态数组实现中删除中间元素需要移动后续元素导致总复杂度退化到O(n²)额外开辟了一个等长的新数组空间开销为O(n)。核心思路把取出换成交换原文档给出了一个巧妙的转换把从数组中取出的元素放入原数组的末尾用交换代替删除第 1 次随机取出一个元素时把它与原数组的倒数第 1 个元素交换第 2 次在剩余元素中随机取出时把它与原数组的倒数第 2 个元素交换依次类推第n-1次最后一次无需交换完成洗牌。这样每一轮处理区间都在缩小第i轮只在尚未固定的前缀区间[0, n-i]内做随机选择被选中的元素与区间末元素交换后即被钉死在后缀区后续不再参与随机。整个过程只做了n-1次交换时间复杂度为O(n)空间复杂度为O(1)原地操作仅需一个临时变量。注原文档特别说明第一次交换选择与倒数第 1 个而不是第 1 个交换是因为与末尾元素交换代码更简洁——倒序遍历使得循环边界与随机区间边界天然一致无需额外维护已固定前缀的游标。参考实现JavaScript原题解给出的 JS 代码如下function shuffle(list) { for (let i list.length - 1; i 1; i--) { const random (Math.random() * (i 1)) 0; const temp list[i]; list[i] list[random]; list[random] temp; } }逐行拆解代码作用for (let i list.length - 1; i 1; i--)从最后一个位置开始倒序处理i同时充当当前待固定区间的末尾下标i 1保证最后一轮只剩 1 个元素无需再交换Math.random()返回[0, 1)区间的均匀随机小数Math.random() * (i 1)映射到[0, i1)覆盖区间0..i共i1个整数候选 0位运算取整等价于Math.floor对非负数为截断得到0..i的均匀随机整数三行交换把list[random]与list[i]互换位置i从此固定关键点剖析随机区间每轮收缩第i轮只在[0, i]内取随机下标保证已经固定到后缀的元素绝不会被再次选中这是等概率成立的结构性前提 0与Math.floor的等价性Math.random() * (i 1)的结果为非负浮点数右移 0 位即向下取整可安全使用若读者希望可读性更强也可改写为Math.floor(Math.random() * (i 1))原地修改函数直接修改传入的list无返回值是典型的原地算法in-place。概率正确性证明原文档给出了完整的数学证明这里完整保留并展开推导。第一步任意一个元素放在任意位置的概率均为1/n。放在倒数第 1 个位置的概率第一次随机即在n个元素中选中它概率为1/n放在倒数第 2 个位置的概率第一次没被选中概率(n-1)/n第二次在剩余n-1个元素中被选中概率1/(n-1)两者相乘仍为1/n放在倒数第k个位置的概率为[(n-1)/n] × [(n-2)/(n-1)] × ... × [(n-k1)/(n-k2)] × [1/(n-k1)] 1/n中间的每一项都是上一轮未被选中的条件概率逐项约分后恰为1/n。因此每个元素等概率地落在每一个位置上。第二步所有排列等概率概率为1/n!。洗牌等价于依次确定第 1 位、第 2 位、……、第 n 位的元素。某一种特定排列出现的概率为1/n × 1/(n-1) × ... × 1/2 × 1 1/n!其中第k步是从剩余n-k1个元素中精确选中该排列指定的那一个。这与每一个排列出现的概率都是1/n!的题目要求完全吻合。这与仓库中 蓄水池抽样reservoid sampling 的证明思路同源蓄水池抽样把最终被选中的概率拆成被选中的概率 × 不被替换的概率逐轮约分后所有元素最终概率均为k/n洗牌则把每个位置的概率逐轮约分恒为1/n。二者都是通过逐轮收缩随机区间保证等概率思想的体现。复杂度分析指标数值说明时间复杂度O(n)恰好执行n-1轮每轮一次随机数生成与一次交换空间复杂度O(1)原地交换仅使用常数级临时变量i、random、temp扩展与变体从洗牌到更广的概率算法这道题的价值不只在于一个函数它连接了仓库中多条概率类知识线1. 蓄水池抽样随机抽样 k 个当数据规模大到无法全部载入内存如数据流场景洗牌算法无法直接使用。蓄水池抽样 用大小为k的蓄水池边遍历边替换保证每个元素被最终选中的概率都是k/n。当k n时蓄水池抽样退化为一次完整洗牌两者算法骨架一致。2. 拒绝采样用 Rand7 实现 Rand10洗牌对随机源的均匀性要求极高。仓库中的 470. 用 Rand7() 实现 Rand10 展示了如何用两次rand7()生成7 × 7 49个等概率结果再从中等概率选出 10 个并拒绝其余采样如行号列号法取idx 40再取模保证输出均匀——这与洗牌算法从均匀分布出发构造等概率结构的思维一脉相承也提醒我们当随机源不够均匀或范围不匹配时需要显式的构造或拒绝策略。3. 概率问题的实验验证仓库的每日一题系列中有多次以实验验证概率结论的先例。例如 三门问题题解 附带的 三门问题模拟程序通过Math.random()驱动 100 万次模拟验证换门胜率 2/3这一违反直觉的结论。洗牌算法同样可以照此思路用大样本模拟验证每种排列频率趋近1/n!或验证每个元素出现在每个位置上的频率趋近1/n。4. 栈混洗stack shuffle仓库 基础数据结构英文版 提到合法的栈混洗操作与合法的括号匹配表达式一一对应n个元素的栈混洗种类数恰等于n对括号的合法表达式数量即卡特兰数。注意这与本文的随机洗牌是不同概念——栈混洗只允许通过入栈/出栈重排讨论的是能产生多少种排列而非如何等概率产生排列二者可对照学习。总结算法本质Fisher-Yates 洗牌通过每轮收缩随机区间 原地交换把抽取操作改为交换操作将时间复杂度从朴素的O(n²)优化到O(n)空间复杂度降为O(1)正确性依据逐轮约分证明每个元素落在任意位置的概率均为1/n进而每种排列出现概率为1/n!严格满足题目要求实现要点倒序遍历、随机区间[0, i]每轮收缩、 0取整、与末尾元素交换保持代码简洁知识延伸与 蓄水池抽样、Rand7 实现 Rand10拒绝采样、三门问题概率实验验证共同构成仓库中一条完整的概率算法学习路径建议结合原文与相关题解对比阅读、动手验证。【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
