高纳德（ Knuth）随机置乱算法，洗牌算法，等概率打乱顺序

- 日理万妓 2023-06-30 13:59 12阅读 0赞

**先看道题：**

从1-100里面随机选出10个的数，你可能会先将100个数存在数组中，用到Math.random函数得到随机下标，从而选出数。

那么如果让你选出10个不同的数呢，你可能会将选出的数先存起来，选第二个数的时候加上一个判断是否选过了。

哪哪哪，如果让你选出90个不同的数呢，是不是你越往后选的时候，重复的越多，这样时间复杂度越高呢

哪我们换个思路，如果将这100个数**打乱**顺序，从中选出前90个，是不是也算是随机选出90个数了呢，所以关键就是如何打乱顺序，才算是随机选出的数。

### 洗牌算法 ###

> Fisher–Yates shuffle 算法由 Ronald Fisher 和 Frank Yates 于 1938 年提出，在 1964 年由 Richard Durstenfeld 改编为适用于电脑编程的版本。

这个算法很牛逼却很好理解，通俗的解释就是：将最后一个数和前面任意 n 个数(包含自己，自己和自己交换)中的一个数进行交换，然后倒数第二个数和前面任意 n-1 个数中的一个数进行交换。。。

> 一副扑克有 54 张牌，有 54! 种排列方式。所谓的打乱指的是，你所执行的操作，应该能够 等概率地生成 这 54! 种结果中的一种。

我们就能设计出一个简单的**暴力算法**了：对于 n 个元素，生成所有的 n! 个排列，然后，随机抽一个。

> 这个算法绝对是公平的。但问题是，复杂度太高。复杂度是多少呢？O(n!)。因为，n 个元素一共有 n! 种排列，我们求出所有 n! 种排列，至少需要 n! 的时间。

> O(n!) 实际上，这是一个比指数级 O(2n) 更高的复杂度。因为 2n 是 n 个 2 相乘；而 n! 也是 n 个数字相乘，但除了 1，其他所有数字都是大于等于 2 的。当 n>=4 开始，n! 以极快的的速度超越 2^n。

> O(2^n) 已经被称为指数爆炸了。O(n!) 不可想象

对于生成的排列，**每一个元素都能等概率地出现在每一个位置。或者反过来，每一个位置都能等概率地放置每个元素。这样就达到了公平了，也就可以说随机了**  
![在这里插入图片描述][20200117223908730.png]  
模拟解释以下算法：

以1、2、3、4、5为例  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMzcxMDA0_size_16_color_FFFFFF_t_70]

第一次从这5个数中随机选一个数。假设为2，则2和末尾的5交换  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMzcxMDA0_size_16_color_FFFFFF_t_70 1]  
那么2出现在最后一位的概率是多少呢？  
5个数中随机选了一个数 **所以p=1/5.**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMzcxMDA0_size_16_color_FFFFFF_t_70 2]  
根据这个算法，我们就已经不用管 2 了，而是在前面 4 个元素中，随机一个元素，放在倒数第二的位置。假设我们随机的是 3。3 和现在倒数第二个位置的元素 4 交换位置

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMzcxMDA0_size_16_color_FFFFFF_t_70 3]  
概率呢？

因为 3 逃出了第一轮的筛选，概率是 4/5，但是 3 没有逃过这一轮的选择。在这一轮，一共有4个元素，所以 3 被选中的概率是 1/4。因此，最终，3 出现在这个倒数第二的位置，概率是 **`4/5 * 1/4 = 1/5。`**

以此类推，第三轮概率为 **`p=(4/5)*(3/4)*(1/3)=1/5`**  
…

知乎大哥：[神一样的随机算法][Link 1]

Java代码：

import java.util.Arrays;
    
    public class Test { 
        public static void main(String[] args) { 
            shuffle();
        }
    
        private static void shuffle() { 
            int[] arr = { 1, 2, 3, 4, 5};
            for (int i = arr.length - 1; i >= 0; i--) { 
                swap(arr, i, (int) (Math.random() * (i + 1)));
            }
            System.out.println(Arrays.toString(arr));
        }
    
        private static void swap(int[] arr, int i, int j) { 
            int n = arr[i];
            arr[i] = arr[j];
            arr[j] = n;
        }

要随机牌的话，将数组中的数字变为扑克牌的数字即可。

[20200117223908730.png]: https://img-blog.csdnimg.cn/20200117223908730.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMzcxMDA0_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200117224539779.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMzcxMDA0,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMzcxMDA0_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200117224543186.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMzcxMDA0,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMzcxMDA0_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200117224649516.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMzcxMDA0,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMzcxMDA0_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200117224730358.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMzcxMDA0,size_16,color_FFFFFF,t_70
[Link 1]: https://mp.weixin.qq.com/s?__biz=MzU4NTIxODYwMQ==&mid=2247484310&idx=1&sn=916f92afff6016256648cfb3c7fd83e7&chksm=fd8cacd0cafb25c670587f22524b111d74b4ddd9954070930b6ef6efb1bd8fba13d4250e57d8&token=885428195&lang=zh_CN#rd