【随机算法】洗牌

摘要: 基于抽取、交换、插入的洗牌算法

【对数据分析、人工智能、金融科技、风控服务感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：潮汐朝夕
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

---

此前我们学习过很多随机算法，并且解决了很多力扣上的相关题目。但是洗牌这个随机算法中最常见的问题，我们还没有解决。

本文我们以力扣 384 为模板题，解决洗牌问题。有三种主流算法：基于抽取、基于交换和基于插入，本文对着三种算法都做了实现。最后我们看一下 std::shuffle 中是如何实现的。

题目

• 384. 打乱数组

给你一个整数数组 nums ，设计算法来打乱一个没有重复元素的数组。打乱后，数组的所有排列应该是 等可能 的。

实现 Solution class:

• Solution(int[] nums) 使用整数数组 nums 初始化对象
• int[] reset() 重设数组到它的初始状态并返回
• int[] shuffle() 返回数组随机打乱后的结果

提示：

1 <= nums.length <= 50
-1e6 <= nums[i] <= 1e6
nums 中的所有元素都是 唯一的
最多可以调用 1e4 次 reset 和 shuffle

示例 1：
输入
[“Solution”, “shuffle”, “reset”, “shuffle”]
[[[1, 2, 3]], [], [], []]
输出
[null, [3, 1, 2], [1, 2, 3], [1, 3, 2]]
解释
Solution solution = new Solution([1, 2, 3]);
solution.shuffle(); // 打乱数组 [1,2,3] 并返回结果。任何 [1,2,3]的排列返回的概率应该相同。例如，返回 [3, 1, 2]
solution.reset(); // 重设数组到它的初始状态 [1, 2, 3] 。返回 [1, 2, 3]
solution.shuffle(); // 随机返回数组 [1, 2, 3] 打乱后的结果。例如，返回 [1, 3, 2]

洗牌算法

(1) 基于抽取 Fisher-Yates Shuffle

基本思想就是从原始数组中随机取一个之前没取过的数字到新的数组中

初始化 vec, new_vec，长度为 n
每一轮从 vec 中取出一个，放到 new_vec 中
当前轮次，vec 的长度为 k
    取 0 <= random_idx < k
    从 vec 中将 k 取出，放入 new_vec
知道 vec 耗尽

正确性证明

一个元素 m 被放进第 i 个位置的概率为 p，为前 i - 1 个位置选择元素时，没有选中 m 的概率乘以第 i 个位置选中 m 的概率

因此

$$p = \frac{n - 1}{n} \times \frac{n-2}{n-1} \times ... \times \frac{n-i+1}{n-i+2} \times \frac{1}{n-i+1} = \frac{1}{n}$$

代码 (C++)

时间 $O(N^{2})$，空间 $O(N)$

class Solution {
public:
    Solution(vector<int>& nums) {
        vec = nums;
        int seed = rand();
        dre = std::default_random_engine(seed);
        dr = std::uniform_real_distribution<double>(0.0, 1.0);
    }

    vector<int> reset() {
        return vec;
    }

    vector<int> shuffle() {
        vector<int> tmp(vec.begin(), vec.end());
        vector<int> result;
        int n = tmp.size();
        for(int i = 0; i < n; ++i)
        {
            int k = tmp.size();
            int random_idx = floor(dr(dre) * k);
            result.push_back(tmp[random_idx]);
            tmp.erase(tmp.begin() + random_idx);
        }
        return result;
    }

private:
    vector<int> vec;
    std::default_random_engine dre;
    std::uniform_real_distribution<double> dr;
};

(2) 基于交换 Knuth-Durstenfeld Shuffle

对基于抽取的 Fisher-Yates Shuffle 的优化。每次抽取出的牌直接交换到原数组尾部，而不是从原数组删掉再插入到新数组。

代码 (C++)

时间 $O(N)$，空间 $O(N)$

class Solution {
public:
    Solution(vector<int>& nums) {
        vec = nums;
        int seed = rand();
        dre = std::default_random_engine(seed);
        dr = std::uniform_real_distribution<double>(0.0, 1.0);
    }

    vector<int> reset() {
        return vec;
    }

    vector<int> shuffle() {
        vector<int> result(vec.begin(), vec.end());
        int n = result.size();
        for(int k = n; k >= 1; --k)
        {
            int random_idx = floor(dr(dre) * k);
            swap(result[random_idx], result[k - 1]);
        }
        return result;
    }

private:
    vector<int> vec;
    std::default_random_engine dre;
    std::uniform_real_distribution<double> dr;
};

(3) 基于插入 Inside-Out Algorithm

Inside-Out Algorithm 算法的基本思思是从前向后扫描数据，把位置 i 的数据随机插入到前 i 个位置中:

插入位置确定：当前是原数组第 i 个位置(vec[i])，取 [0, i] 范围的随机下标 random_idx = floor(dr(dre) * (i + 1))，
将 vec[i] 放进新数组的 random_idx ，但该位置可能已经插入了前面的值。此时将原有的值交换到新数组的 i 位置(此位置当前肯定没有插入过元素)。

其实效果相当于新数组中位置 k 和位置 i 的数字进行交互。

正确性证明

对于 nums[i]，在新数组中的位置为 j。

• 0 <= j <= i

第 i 次刚好随机放到了 j 位置，在后面的 n - i 次选择中该数字不被选中

$$p(j) = \frac{1}{i} \times \frac{i}{i+1} \times \frac{i+1}{i+2} \times ... \times \frac{n-1}{n} = \frac{1}{n}$$

• i + 1 <= j < n

假设是第 k 次 (i+1 <= k < n) 随机到了 j 位置。在后面的 n-k 次选择中该数字不被选中。

$$p(j) = \frac{1}{k} \times \frac{k}{k+1} \times \frac{k+1}{k+2} \times ... \times \frac{n-1}{n} = \frac{1}{n}$$

代码 (C++)

时间 $O(N)$，空间 $O(N)$

class Solution {
public:
    Solution(vector<int>& nums) {
        vec = nums;
        int seed = rand();
        dre = std::default_random_engine(seed);
        dr = std::uniform_real_distribution<double>(0.0, 1.0);
    }

    vector<int> reset() {
        return vec;
    }

    vector<int> shuffle() {
        int n = vec.size();
        vector<int> result(n);
        for(int i = 0; i < n; ++i)
        {
            int random_idx = floor(dr(dre) * (i + 1));
            swap(result[random_idx], result[i]);
            result[random_idx] = vec[i];
        }
        return result;
    }

private:
    vector<int> vec;
    std::default_random_engine dre;
    std::uniform_real_distribution<double> dr;
};

std::shuffle

直接调用

对于前面的洗牌问题，当然我们可以直接调用 std::shuffle 解决，代码如下：

class Solution {
public:
    Solution(vector<int>& nums) {
        vec = nums;
    }

    vector<int> reset() {
        return vec;
    }

    vector<int> shuffle() {
        vector<int> result = vec;
        int seed = rand();
        std::default_random_engine dre(seed);
        std::shuffle(result.begin(), result.end(), dre);
        return result;
    }

private:
    vector<int> vec;
};

算法

std::shuffle 的实现方式的核心是下面这段代码，详细内容可以参考《计算机程序设计艺术》 $3-4-2。

void shuffle(RandomAccessIterator first, RandomAccessIterator last, RandomNumberGenerator& rand)
{
    if(first == last) return;
    for(auto i = first + 1; i != last; ++i)
        iter_swap(i, first + rand((i - first) + 1));
}

代码 (C++)

用 std::shuffle 的实现方式解决力扣 384 的完整代码如下：

class Solution {
public:
    Solution(vector<int>& nums) {
        vec = nums;
        int seed = rand();
        dre = std::default_random_engine(seed);
        dr = std::uniform_real_distribution<double>(0.0, 1.0);
    }

    vector<int> reset() {
        return vec;
    }

    vector<int> shuffle() {
        vector<int> result = vec;
        shuffle(result.begin(), result.end(), dre);
        return result;
    }

private:
    void shuffle(vector<int>::iterator first, vector<int>::iterator last, std::default_random_engine& rand)
    {
        if(first == last) return;
        std::uniform_real_distribution<double> dr(0.0, 1.0);
        for(auto i = first + 1; i != last; ++i)
            iter_swap(i, first + floor(dr(rand) * (i - first + 1)));
    }

    vector<int> vec;
    std::default_random_engine dre;
    std::uniform_real_distribution<double> dr;
};

---