洗牌算法

2019-08-01 algorithm leetcode

需要保证是一个公平的随机算法，首先介绍如何打乱，然后是如何判断已经打乱，也就是符合均匀分布，满足公平。

洗牌算法

在介绍时会包含了两个基本的算法 Fisher-Yates Shuffle 以及 Knuth-Durstenfeld Shuffle ，一般会说后者是通过前者优化得来，但怎么感觉后者只是前者的计算机实现而已，所以还是只介绍后者的实现吧。

Knuth-Durstenfeld Shuffle

每次从未处理的数据中随机取出一个数字，然后把该数字与尾部的数值进行交换，这样数组尾部存放的是已经处理过的数字。

出现在各个位置的概率计算如下。

  • 出现在第 $n-1$ 位置处的概率为 $\frac{1}{n}$ 。
  • 出现在第 $n-2$ 位置处的概率为 $\frac{n-1}{n} \times \frac{1}{n-1}$ 。
  • … …
  • 出现在第 $n-k$ 位置处的概率为 $\frac{n-1}{n} \times \frac{1}{n-1} \times \cdots \times \frac{n-k+1}{n-k+2} \times \frac{1}{n-k+1}=\frac{1}{n}$ 。

如下是一个简单的示例。

#include <time.h>
#include <stdio.h>
#include <stdlib.h>

/* random value in [min, max] */
int do_random(int min, int max)
{
        return rand() % (max - min) + min;
}

void swap(int *arr, int i, int j)
{
        int t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
}

void shuffle(int *arr, int n)
{
        int i, rnd;

        for (i = 0; i < n - 1; i++) {
                rnd = do_random(i, n - 1);
                swap(arr, i, rnd);
        }
}

#define S 6
#define N 40000

int main(void)
{
        int i, j;
        int count[S] = {0};
        int array[S] = {0, 1, 2, 3, 4, 5};

        srand(time(NULL));
        for (i = 0; i < N; i++) {
                shuffle(array, S);
                for (j = 0; j < S; j++) {
                        if (array[j] == 0) {
                                count[j]++;
                                break;
                        }
                }
        }

        for (i = 0; i < S; i++)
                printf("%2d  %d\n", i, count[i]);
        return 0;
}

其中，对于判断条件 i < n - 1 来说，在只剩下了最后一个元素时，不再调用随机函数，这样一来随机函数的处理也会比较简单，无需判断边界是否相等。

还有一种，判断条件为 i < n ，也就是在剩下最后一个元素时，仍然会再调用一次 do_random() 函数，此时 max 与 min 相等，所以在函数中需要坐下处理，函数修改为。

int do_random(int min, int max)
{
        if (min == max)
				return min;
        return rand() % (max - min) + min;
}

另外，还可以反向进行计算，对应的判断条件为。

for (i = n - 1; i > 0; i--) {
        rnd = do_random(0, i);

for (i = n - 1; i >= 0; i--) {
        rnd = do_random(0, i);

对于边界的处理与上面的方式相同。

在验证的时候，可以统计某个位出现在各个位置的概率，如上是统计 0 出现在各个位置的次数。

蓄水池采样

其场景为，对一个很大的总体抽取 $K$ 个样本，总体可能会很大，无法完全放到内存中，也有可能不确定其大小。

这也就是要讲到的蓄水池采样算法 (Reservoir Sampling)，假设总体为 $N$ ，然后采样 $K$ 个，那么其执行过程为：

  1. 构建一个可容纳 $K$ 个元素的数组，将序列的前 $K$ 个元素放入数组中。
  2. 从第 $K+1$ 个元素开始，以 $\frac{k}{k+1}$ 的概率来决定该元素是否被替换到数组中。
  3. 重复上一步骤，直到遍历完所有元素，剩下的元素就是所需采样的样本。

接下来，证明每个元素可能被采样的概率均为 $\frac{k}{n}$ 。

概率证明

对于第 $i \ (i \leqslant k)$ 个元素来说，在第 $k$ 步前被选中的概率为 $1$ ，当走到第 $k+1$ 步时，被 $k+1$ 个元素替换的概率为 $k+1$ 个元素被选中，且第 $i$ 被选中替换，也就是 $\frac{k}{k+1}\times \frac{1}{k}=\frac{1}{k+1}$ ，那么被保留的概率为 $1-\frac{1}{k+1}=\frac{k}{k+1}$ 。

依次类推，可以得到不被 $k+2$ 个元素替换的概率为 $\frac{k+1}{k+2}$ ，那么当运行到第 $n$ 步时，被保留的概率为，被选中且不被替换的概率，也就是。

$$1 \times \frac{k}{k+1} \times \frac{k+1}{k+2} \times \cdots \times \frac{n-1}{n}=\frac{k}{n}$$

同样，对于第 $j \ (j > k) $ 个元素来说，其在第 $j$ 步中被选中的概率为 $\frac{k}{j}$ ，而不被 $j+1$ 个元素替换掉的概率为 $1-\frac{1}{j+1} \times \frac{1}{k}=\frac{1}{j+1}$ 。那么，运行到第 $n$ 步时，被保留的概率同样为，被选中且不被替换的概率，也就是：

$$\frac{k}{j} \times \frac{j}{j+1} \times \frac{j+1}{j+2} \times \cdots \times \frac{n-1}{n}=\frac{k}{n}$$

也就是说，每个元素被保留的概率为 $\frac{k}{n}$ 。

代码实现

实现的采样代码以及测试如下。

#include <time.h>
#include <stdio.h>
#include <stdlib.h>

void sampling(int *data, int k, int *pool, int n)
{
        int rnd, i;

        for (i = 0; i < k; i++)
                data[i] = pool[i];

        for (i = k; i < n; i++) {
                rnd = rand() % (i + 1);
                if (rnd < k)
                        data[rnd] = pool[i];
        }
}

#define N   10
#define K   5
#define CNT 60000

int main(void)
{
        int i, j, data[K];
        int array[N] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
        int count[N] = {0};

        srand(time(NULL));
        for (i = 0; i < CNT; i++) {
                sampling(data, K, array, N);
                for (j = 0; j < K; j++)
                        count[data[j]]++;
        }

        for (i = 0; i < N; i++)
                printf("%2d  %d\n", i, count[i]);

        return 0;
}

参考