【算法】洗牌算法

怼烎@ 2023-10-07 22:56 22阅读 0赞

#### 目录 ####

*  1.概述
 *  2.代码实现
 *   *  2.1.暴力法
     *  2.2.Fisher-Yates 洗牌算法
 *  3.应用

> 本文参考：  
> LeetCode [384. 打乱数组][384.]

## 1.概述 ##

（1）洗牌算法可以理解为：设计算法来打乱一个没有重复元素的数组 nums，并且打乱后，**数组的所有排列应该是等可能的**。

（2）假设数组 nums 的长度为 n，数组 nums 的全排列有 n! 种，也就是说打乱后的结果总共有 n! 种。因此设计的洗牌算法必须能够产生的结果必须有 n! 种可能，否则就是错误的。

## 2.代码实现 ##

下面分别使用暴力法和 Fisher-Yates 洗牌算法来实现实现 Solution class：

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

### 2.1.暴力法 ###

（1）暴力法的基本思想如下：

*  将长度为 n 的数组 nums 中所有的数都放到 list 中，并初始化打乱后的数组 shuffle；
 *  循环 n 次，在第 i 次循环中 (0 ≤ i < n)：
    
     *  在 list 中随机抽取一个数 num，将其作为打乱后的数组 shuffle 的第 i 个元素；
     *  从 list 中移除 num；

（2）对于原数组 nums 中的数 num 来说，被移动到打乱后的数组的第 i 个位置的概率为：

![在这里插入图片描述][e964700e602242ac83872342fe47c505.png]

因此，**原数组 nums 中的任意一个数被移动到打乱后的数组的任意一个位置的概率都是相同的。**

（3）具体的代码实现如下：

import java.util.ArrayList;
    import java.util.List;
    import java.util.Random;
    
    class Solution1 {
        
        //当前数组
        int[] nums;
        //初始数组
        int[] oriNums;
        
        //构造函数：使用整数数组 nums 初始化对象
        public Solution1(int[] nums) {
        
            this.nums = nums;
            this.oriNums = new int[nums.length];
            System.arraycopy(nums, 0, oriNums, 0, nums.length);
        }
        
        //重设数组 nums 到它的初始状态并返回
        public int[] reset() {
        
            System.arraycopy(oriNums, 0, nums, 0, nums.length);
            return nums;
        }
        
        //返回数组 nums 随机打乱后的结果
        public int[] shuffle() {
        
            // shuffled 为打乱后的数组
            int[] shuffled = new int[nums.length];
            List<Integer> list = new ArrayList<>();
            for (int i = 0; i < nums.length; ++i) {
        
                list.add(nums[i]);
            }
            Random random = new Random();
            for (int i = 0; i < nums.length; ++i) {
        
                //nextInt(bound):随机生成 [0, bound) 之间的一个整数并返回
                int j = random.nextInt(list.size());
                shuffled[i] = list.remove(j);
            }
            System.arraycopy(shuffled, 0, nums, 0, nums.length);
            return nums;
        }
    }
    
    /**
     * Your Solution object will be instantiated and called as such:
     * Solution obj = new Solution(nums);
     * int[] param_1 = obj.reset();
     * int[] param_2 = obj.shuffle();
     */

### 2.2.Fisher-Yates 洗牌算法 ###

（1）考虑通过调整 list 的实现方式以上述方法：

*  我们可以在移除 list 的第 k 个元素时，将第 k 个元素与数组的最后 1 个元素交换，然后移除交换后数组的最后 1 个元素，这样我们只需要 O(1) 的时间复杂度即可完成移除第 k 个元素的操作。此时，被移除的交换后数组的最后 1 个元素即为我们根据随机下标获取的元素。
 *  在此基础上，我们也可以不移除最后 1 个元素，而直接将其作为乱序后的结果，并更新待乱序数组的长度，从而实现数组的原地乱序。因为我们不再需要从数组中移除元素，所以也可以将第 k 个元素与第 1 个元素交换。

（2）具体地，实现算法如下：

*  设待打乱的数组为 nums，其长度为 n。
 *  循环 n 次，在第 i 次循环中 (0 ≤ i < n)：
    
     *  在 \[i,n) 中随机抽取一个下标 j；
     *  将第 i 个元素与第 j 个元素交换；

其中数组 nums 中的 nums\[i … n−1\] 为待打乱的部分，其长度为 n - i；nums\[0 … i−1\] 则为打乱后的部分，其长度为 i。

（3）具体的代码实现如下：

class Solution {
        
        //当前数组
        int[] nums;
        //初始数组
        int[] oriNums;
        
        //构造函数：使用整数数组 nums 初始化对象
        public Solution(int[] nums) {
        
            this.nums = nums;
            this.oriNums = new int[nums.length];
            //将 nums 中的元素复制到 oriNums 中
            System.arraycopy(nums, 0, oriNums, 0, nums.length);
        }
        
        //重设数组 nums 到它的初始状态并返回
        public int[] reset() {
        
            //将 oriNums 中的元素复制到 nums 中，即完成回到初始化状态
            System.arraycopy(oriNums, 0, nums, 0, nums.length);
            return nums;
        }
        
        //返回数组 nums 随机打乱后的结果
        public int[] shuffle() {
        
            Random random = new Random();
            int length = nums.length;
            //洗牌算法
            for (int i = 0; i < length; i++) {
        
                //nextInt(bound):随机生成 [0, bound) 之间的一个整数并返回
                int j = i + random.nextInt(length - i);
                //交换 nums[i] 和 nums[j]
                int tmp = nums[i];
                nums[i] = nums[j];
                nums[j] = tmp;
            }
            return nums;
        }
    }
    
    /**
     * Your Solution object will be instantiated and called as such:
     * Solution obj = new Solution(nums);
     * int[] param_1 = obj.reset();
     * int[] param_2 = obj.shuffle();
     */

## 3.应用 ##

大家可以去 LeetCode 上找相关的洗牌算法的题目来练习，或者也可以直接查看[LeetCode算法刷题目录 (Java)][LeetCode_ _Java]这篇文章中的洗牌算法章节。如果大家发现文章中的错误之处，可在评论区中指出。

[384.]: https://leetcode.cn/problems/shuffle-an-array/solution/da-luan-shu-zu-by-leetcode-solution-og5u/
[e964700e602242ac83872342fe47c505.png]: https://img-blog.csdnimg.cn/e964700e602242ac83872342fe47c505.png
[LeetCode_ _Java]: https://blog.csdn.net/weixin_43004044/article/details/122477673