洗牌算法

又名shuffle算法

背景

首先要明白这个算法的目的：打乱——等概率地穷举出所有可能的排列顺序。
就是字面意思，类似打乱一副扑克牌；实际应用可以是班级内的随机点名之类有限元随机问题

基本思想

假设有n个元素，那么由初等数学可知他们共有n! 种排序方式。
洗牌算法即模拟日常生活中的洗牌，基本操作是：从i=0处开始，每次在（i,n)之间随机选择一个数字与i进行交换，直到最后一个数字；一共会产生（n-1)x(n-2)x(n-3)x...即n! 种可能，而且是随机的。

class Solution {
    Random random = new Random();
    public int[] shuffle(int target) {
        int[] ans = target.clone();
        int n = ans.length;
        for (int i = 0; i < n; i++) {
            swap(ans, i, i + random.nextInt(n - i));
        }
        return ans;
    }
    void swap(int[] arr, int i, int j) {
        int c = arr[i];
        arr[i] = arr[j];
        arr[j] = c;
    }
}

水池抽样

这个算法有一些特殊的应用场景；比如说从一个十分长的队列中随机选择k个数字出来，要求每一个数字被选到的概率相同，就可以用到这种算法。

基本思想

从k=1的情况开始：
也就是说，我们每次只能读一个数据。

假设数据流含有N个数，我们知道如果要保证所有的数被抽到的概率相等，那么每个数抽到的概率应该为 1/N

那如何保证呢？

先说方案：

每次只保留一个数，当遇到第 i 个数时，以 1/i的概率保留它，(i-1)/i的概率保留原来的数。

举例说明：

遇到1，概率为1，保留第一个数。
遇到2，概率为1/2，这个时候，1和2各1/2的概率被保留
遇到3，3被保留的概率为1/3，(之前剩下的数假设1被保留)，2/3的概率 1 被保留，(此时1被保留的总概率为 2/3 1/2 = 1/3)
遇到4，4被保留的概率为1/4，(之前剩下的数假设1被保留)，3/4的概率 1 被保留，(此时1被保留的总概率为 3/4 2/3 * 1/2 = 1/4)

以此类推，每个数被保留的概率都是1/N。可用数学归纳法证明；

接下来是k=m时：
也就是说，我们每次能读m个数据。
和上面相同的道理，只不过概率在每次乘以了m而已

代码实现

即力扣382.链表随机节点的题解

class Solution {
    ListNode head;
    Random random;

    public Solution(ListNode head) {
        this.head = head;
        random = new Random();
    }

    public int getRandom() {
        int i = 1, ans = 0;
        for (ListNode node = head; node != null; node = node.next) {
            if (random.nextInt(i) == 0) { // 1/i 的概率选中（替换为答案）
                ans = node.val;
            }
            ++i;
        }
        return ans;
    }
}

　碎碎念

这一个问题可以说是我人生遇到的第一个算法问题了吧；
遥想当年肝了一个十一（还是五一来着）假期，在没有安卓编程基础，只会点三脚猫java的情况下，用一台手机码代码，照着各种教程，硬是码出了一个“点名器”app，送给了我们最和蔼的语文老师用来点名背古诗233333.不过当时实在是没有什么算法的概念，随机点名只是把人名存成了一个数组，每次从里面随机拿出来一个罢了；导致重复率相当的高，效果并不算好。
直到今天力扣每日一题刷到了一个蓄水池算法，突然激起了遥远的回忆哈，遂作此篇。