两种随机算法

　　今天偶然看到一篇博文在讲游戏地图的随机生成算法，遂将其整理在此处备份。

　　以扫雷游戏为例，扫雷游戏中的炸弹是随机生成的，那怎么保证生成的随机性呢？对于扫雷地图而言，可以抽象为一个二维矩阵m*n，炸弹数量为k，则问题可能概括为在m*n的二维数组中随机抽取k个数。

　　这儿的扫雷棋盘可以用下面的类表示。

class Game
{
public:    
    int m,n;
　　//大小为m*n的棋盘
　　//true表示有炸弹，false表示没有炸弹
    std::vector<std::vector<bool>> board(m,std::vector<bool>(n,false));
}；

　　对于在二维数组选择k个位置，可以将二维数组降维成一个长度为m*n的一维数组，问题就转换成在一维数组中随机提取k个数。二维数组和一维数组的转换方法如下。

class Game
{
    ...
    struct Point
    {
　　　　int x;
　　　　int y;
　　};
    //将二维数组的坐标（x，y）转换成一维数组中的索引
    int encode(const Point& point)
    {
        return point.x*n+point.y;
    }
    //将一维索引转换成二维坐标
    Point decode(int index)
    {
　　　　Point point;
　　　　point.x = index/n;
　　　　point.y = index%n;
　　　　return point;
    }
}；

　　将问题转换成在一个长度为L的一维数组中随机抽取k个数，相信很多人都可以很快的写出一种解法，那就是随机抽样法。

　　随机抽样实现的伪代码为

输出一维数组array_out  RandomSampling（输入一维数组array_in，抽样数k）
{
　　for（int i= 0； i< k; ++i）
　　{
　　　　在array_in中随机抽取一个元素放入到array_out中
　　}
}

　　对于上述解法的随机性可以用数学格式验证，在长度为L中的数组中抽取k个数的组合数为( L! ) / [ ( L – k ) ! ]。

　　在这种实现下，还有优化的地方，那就是空间复杂度。我们可以将抽取的k个数放在输入数组的前k个位置。

void RandomSampling（输入一维数组array_in， 抽样数k）
{
　　int n = array_in.size();
　　　for(int i = 0; i < k; )
　　{
　　　　int idx = rand()%(n-i) + i;  //从[i,array_in.size）中随机一个索引
　　　　swap（array_in[i], array_in[idx]）;  //将随机到的元素存放在数组前面，数组[i, array_in.size)区域的抽样区域
　　　　++i;
　　}
}

　　对于上述写法，可能有些同学会想到，将元素array_in[i]放到后面的位置，会不会影响到其随机性，事实上，这是不会的。因为对于抽样区域，元素可以认为是无序的，所以本质上并没有先后顺序。

　　所以，在长度为L的数组中抽样k个元素的问题就这么解决了。那么，当k等于L呢，这就涉及到“洗牌算法”了。洗牌算法的本质和随机抽样法的优化版本是一致的。既在空间复杂度为O（1）、时间复杂度为O（n）下，将数组随机重排。当数组长度为n时，结果即为n的全排列 n！。伪代码为。

void shuffle（输入一维数组array_in）
{
　　int n = array_in.size;
　　for(int i = 0; i < n; ++i)
　　{
　　　　int idx = rand()%(n-i) + i;
　　　　swap(array_in[idx], array_in[i]);
　　}
}

　　在讲完“洗牌算法”之后，我们可以解决l已知长度的数组中随机抽样的方法。但是，当数组长度未知呢，当数据结构为链表呢，如果要求遍历一次得出结果，那我们就无法使用“洗牌算法”了。

　　下面，我们就来介绍一下“水塘抽样算法”。“水塘抽样算法”，顾名思义也是抽样，既在顺序遍历过程中，判断当前节点是否要抽样，如果要则用当前节点覆盖抽样结果，等到遍历结束后，抽样结果输出为整体抽样结果。

　　很明显，在这个过程中，抽样判断是至关重要的一环，那么抽样判断的条件是什么呢。

　　对于n个元素中只抽样一个的情况下，即要保证每个元素的抽样概率为1/n。对于第i个元素，其为抽样结果的概率的计算公式（1）为。

　　等号左侧第一项是第i个元素被抽样的概率，第二项是第i+1个元素不被抽样的概率，后面的项以此类推。对于第i个元素之前的元素，其被抽样的情况对第i个元素没有影响。伪代码为。

//返回链表中的一个随机节点值
int getRandom（ListNode* phead）
{
　　int i = 0; //用于记录遍历的链表节点数
　　int res = 0；
　　ListNode* p = phead；
　　while（p）
　　{
　　　　++i;
　　　　if(rand()%i == 0)  //生成[0,i)之间的随机数，这个随机数为0的概率就是1/i
　　　　{
　　　　　　res = p->value;
　　　　}
　　　　p = p->next;
　　}
　　return res;
}

　　同理，如果是在单链表中随机选择k个数，根据上面的数学公式（1）可以很快得出，第i个元素的被抽样的概率为

　　第i+1个元素不被抽样的概率同理为 

　　对于代码实现，也就是将 rand()%i == 0换成rand()%i < k

　　那么，抽样得到的元素，应该覆盖k个结果中的哪一个呢。应该保证抽样元素覆盖k个结果中的每一个概率都为1/k；而上述随机的结果范围为[0,k)间的整数，每一个出现的概率又是1/k。那么，也就是说我们可以把随机数看作抽样得到的元素应该覆盖的索引。则伪代码可以修改为

int[] getRandom（ListNode* pHead， int k）
{
　　int i = 0;
　　int ans[k];
　　while(pHead)
　　{
　　　　++i;
　　　　int j = 0;
　　　　if((j = rand()%i) < k)
　　　　{
　　　　　　ans[j] = pHead->value;
　　　　}
　　　　pHead = pHead->next;
　　}
　　return ans;
}

　　在此，“洗牌算法”和“池塘抽样法”就介绍的差不多了，那我们怎么检查随机算法的正确性呢（在很多时候，数学推导公式正确，但是在编写代码时却出现编了写错误）。这儿我们使用“蒙特卡洛验证法”（本质是大力出奇迹，暴力）。

　　对于“池塘抽样方式”，我们可以在[12,22)中随机选3个数，然后重复10万次，看每个元素被选中的次数是否相同。

　　对于“洗牌算法”，我们可以跟踪一个元素，记录其中多次打乱后的每一次索引值，如果落在各个索引的次数基本相同，则算法正确。

今天的文章两种随机算法分享到此就结束了，感谢您的阅读，如果确实帮到您，您可以动动手指转发给其他人。