最早提出这个洗牌方法的是 Ronald A. Fisher 和 Frank Yates,即 Fisher–Yates Shuffle,其基本思想就是从原始数组中随机取一个之前没取过的数字到新的数组中,具体如下:
初始化原始数组和新数组,原始数组长度为n(已知);
从还没处理的数组(假如还剩k个)中,随机产生一个 [0,k) 之间的数字p(假设数组从0开始);
从剩下的k个数中把第p个数取出;
重复步骤2和3直到数字全部取完;
从步骤3取出的数字序列便是一个打乱了的数列。
下面证明其随机性,即每个元素被放置在新数组中的第 i 个位置是 1/n (假设数组大小是n)。
P=nn−1×n−1n−2×…×n−i+2n−i+1×n−i+11=n1
void Fisher_Yates_Shuffle(vector<int>& arr,vector<int>& res)
{
int len = arr.size();
srand((unsigned)time(NULL));
for (int i = 0; i < len; ++i)
{
int k = rand() % arr.size();
res.push_back(arr[k]);
arr.erase(arr.begin() + k);
}
}
在n-2个位置概率是 [(n−1)/n][1/(n−1)]=1/n,(第一次交换的随机数不为 i ,第二次为arr[i]所在的位置(注意,若 i=n−1 ,第一交换arr[n-1]会被换到一个随机的位置))
在第n-k个位置的概率是 [(n−1)/n]×[(n−2)/(n−1)]×…×[(n−k+1)/(n−k+2)]×[1/(n−k+1)]=1/n(第一个随机数不要为 i ,第二次不为arr[i]所在的位置(随着交换有可能会变)......第 n−k 次为arr[i]所在的位置)。
void Knuth_Durstenfeld_Shuffle(vector<int> &arr)
{
int len = arr.size();
srand((unsigned)time(NULL));
for (int i = len - 1; i >= 0; --i)
{
int k = rand() % (i + 1);
swap(arr[k], arr[i]);
}
}