如何用 Fisher-Yates 洗牌保证数组随机排列等概率？（LeetCode 384）

简化版

Fisher-Yates 洗牌从左到右或从右到左都可以。常见写法是从 i=0 到 n-1，在 [i,n-1] 中随机选一个位置 j，交换 nums[i] 和 nums[j]。这样每个排列出现概率都是 1/n!。

详细版

class Solution {
    private int[] origin;
    private Random random = new Random();

    public Solution(int[] nums) {
        origin = nums.clone();
    }

    public int[] reset() {
        return origin.clone();
    }

    public int[] shuffle() {
        int[] a = origin.clone();
        for (int i = 0; i < a.length; i++) {
            int j = i + random.nextInt(a.length - i);
            int tmp = a[i];
            a[i] = a[j];
            a[j] = tmp;
        }
        return a;
    }
}

关键是第 i 步只能从尚未固定的位置里选，不能每次都从全数组随机交换，否则排列概率会不均匀。

完整版教学

一、洗牌题的目标是什么

不是“看起来随机”，而是所有排列等概率。长度为 n 的数组有 n! 种排列，每一种都应该以 1/n! 的概率出现。

[1,2,3] 有 6 种排列
每种概率都应是 1/6

如果算法让某些排列更容易出现，就不是合格洗牌。

二、Fisher-Yates 的过程

从左往右固定位置：

i=0，从 [0,n-1] 选一个元素放到 0
i=1，从 [1,n-1] 选一个元素放到 1
i=2，从 [2,n-1] 选一个元素放到 2

每一步都只在未固定区间里随机选择。

步骤	随机范围	固定的位置
`i=0`	`[0,n-1]`	第 0 位
`i=1`	`[1,n-1]`	第 1 位
`i=k`	`[k,n-1]`	第 k 位

记忆钩子：洗牌不是乱交换很多次，而是“每一位从剩余牌里公平抽一张”。

三、为什么概率是均匀的

第 0 位每个元素被选中的概率是 1/n；第 1 位在剩余 n-1 个元素中均匀选择，概率是 1/(n-1)；依此类推。

某个具体排列出现的概率：

1/n * 1/(n-1) * ... * 1/1 = 1/n!

所以所有排列概率一致。

四、为什么不能每次都随机全数组交换

如果每一轮都随机两个位置交换固定次数，排列空间不一定被均匀覆盖。对于小数组，可以算出不同排列出现次数不均。

Fisher-Yates 的优势是每一步都把一个位置定死，并且选择范围正好是剩余元素数，天然匹配 n! 的分解。

五、`reset` 为什么要返回原数组副本

如果直接返回 origin，调用方可能修改内部数组，破坏后续洗牌。

public int[] reset() {
    return origin.clone();
}

构造函数里也要保存 nums.clone()，避免外部数组后续被改动影响对象状态。

六、随机边界如何写

Java 中 random.nextInt(bound) 返回 [0,bound)。要在 [i,n-1] 中选：

int j = i + random.nextInt(n - i);

如果写成 random.nextInt(n)，就可能选到已经固定的位置，破坏等概率证明。

七、常见误区与追问

误区：每轮从整个数组随机位置交换。 已固定位置会被重新扰动，概率证明不成立。
误区：返回内部原数组。 调用方可能修改内部状态，应返回 clone。
误区：随机范围少包含最后一个元素。 nextInt 上界是开区间，边界要写准。
追问：为什么每种排列概率是 1/n!？ 每位从剩余元素中均匀选，概率连乘。
追问：时间和空间复杂度？ 洗牌 O(n)，返回新数组需要 O(n) 空间。
追问：能否原地洗牌？ 可以，但 LeetCode 设计通常保留原数组用于 reset。

八、加强记忆

Fisher-Yates 洗牌就是“第 i 位从 [i,n-1] 随机抽一张牌来放”。这个范围是灵魂。概率证明也很短：1/n * 1/(n-1) * ... * 1 = 1/n!，所以每个排列等概率。

简化版

详细版