Sep 8, 2019

线性空间随机算法（洗牌算法）

Fisher-Yates Shuffle算法

最早提出这个洗牌方法的是 Ronald A. Fisher 和 Frank Yates，即 Fisher–Yates Shuffle，其基本思想就是从原始数组中随机取一个之前没取过的数字到新的数组中，具体如下：

初始化原始数组和新数组，原始数组长度为n(已知)；
从还没处理的数组（假如还剩k个）中，随机产生一个[0, k)之间的数字p（假设数组从0开始）；
从剩下的k个数中把第p个数取出；
重复步骤2和3直到数字全部取完；
从步骤3取出的数字序列便是一个打乱了的数列。

#define N 10
#define M 5
void Fisher_Yates_Shuffle(vector<int>& arr,vector<int>& res)
{
     srand((unsigned)time(NULL));
     int k;
     for (int i=0;i<M;++i)
     {
     	k=rand()%arr.size();
     	res.push_back(arr[k]);
     	arr.erase(arr.begin()+k);
     }
}

该算法最原始的设计是在第三步时，遍历p次找到需要取出的数，这样在最坏的情况下，时间复杂度为O(n^2)，空间复杂度为O(n)。改进为按下标随机抽取，可以优化到O(n)的时间复杂度

Knuth-Durstenfeld Shuffle算法

Knuth 和 Durstenfeld在Fisher等人的基础上对算法进行了改进，在原始数组上对数字进行交互，省去了额外O(n)的空间。该算法的基本思想和 Fisher 类似，每次从未处理的数据中随机取出一个数字，然后把该数字放在数组的尾部，即数组尾部存放的是已经处理过的数字。算法步骤为：

建立一个数组大小为 n 的数组 arr，分别存放 1 到 n 的数值；
生成一个从 0 到 n - 1 的随机数 x；
输出 arr 下标为 x 的数值，即为第一个随机数；
将 arr 的尾元素和下标为 x 的元素互换；
同2，生成一个从 0 到 n - 2 的随机数 x；
输出 arr 下标为 x 的数值，为第二个随机数；
将 arr 的倒数第二个元素和下标为 x 的元素互换；

如上，直到输出 m 个数为止

void Knuth_Durstenfeld_Shuffle(vector<int>&arr)
{
	for (int i=arr.size()-1;i>=0;--i)
	{
		srand((unsigned)time(NULL));
		swap(arr[rand()%(i+1)],arr[i]);
	}
}

时间复杂度为O(n),空间复杂度为O(1),缺点必须知道数组长度n. 由于需要知道未排序区间长度，所以无法处理不知道长度或动态增长的数组。

Inside-Out Algorithm算法

Knuth-Durstenfeld Shuffle 是一个内部打乱的算法，算法完成后原始数据被直接打乱，尽管这个方法可以节省空间，但在有些应用中可能需要保留原始数据，所以需要另外开辟一个数组来存储生成的新序列。 Inside-Out Algorithm 算法的基本思思是从前向后扫描数据，把位置i的数据随机插入到前i个（包括第i个）位置中（假设为k），这个操作是在新数组中进行，然后把原始数据中位置k的数字替换新数组位置i的数字。其实效果相当于新数组中位置k和位置i的数字进行交互。如果知道arr的lengh的话，可以改为for循环，由于是从前往后遍历，所以可以应对arr[]数目未知的情况，或者arr[]是一个动态增加的情况。

void Inside_Out_Shuffle(const vector<int>&arr,vector<int>& res)
{
	res.assign(arr.size(),0);
	copy(arr.begin(),arr.end(),res.begin());
	int k;
	for (int i=0;i<arr.size();++i)
	{
		srand((unsigned)time(NULL));
		k=rand()%(i+1);
		res[i]=res[k];
		res[k]=arr[i];
	}
}

时间复杂度为O(n),空间复杂度为O(n).

蓄水池抽样

从N个元素中随机等概率取出k个元素，N长度未知。它能够在o（n）时间内对n个数据进行等概率随机抽取。如果数据集合的量特别大或者还在增长（相当于未知数据集合总量），该算法依然可以等概率抽样. 伪代码：

Init : a reservoir with the size： k  
        for    i= k+1 to N  
            M=random(1, i);  
            if( M < k)  
                 SWAP the Mth value and ith value  
       end for

上述伪代码的意思是：先选中第1到k个元素，作为选中元素区间。然后依次对未选中区间中的第k+1至第N个元素做如下操作：设x是元素的序号，随机在1到x区间内生成一个数字，如果该数字存在于选中区间，则该下标的元素与x号元素进行交换。这样每个元素都有k/x的概率被选中，然后等概率（1/k）替换掉选中区间的元素。

void Reservoir_Sampling(vector<int>& arr)
{
	int k;
	for (int i=M;i<arr.size();++i)
	{
		srand((unsigned)time(NULL));
		k=rand()%(i+1);
		if (k<M)
			swap(arr[k],arr[i]); 
	}
}