image
斗地主相信大家都玩过
每次输了之后都要仔细认真的洗牌
确保自己下一局拿到的牌是公平的
对牌局来说，洗牌洗的越乱越随机
那么对每个参与游戏的人来说越公平
小编在编程过程中
经常会遇到这样的操作
给定以下一串数组
image
怎么得到1-7的乱序全排列呢
起初，我的想法是
任意交换两个元素的位置
循环N次……使劲打乱顺序
image
这样做每个元素被选中的概率似乎一样
但是这个循环次数N要该怎么取值合理呢
当序列长度过长时，时间复杂度也会爆炸
那么
电脑中的洗牌算法是怎样实现
又是怎么保证公平的呢
接下来就介绍三种简单常用
而且保证公平的洗牌算法
1.Fisher_Yates_Shuffle算法
简单来说就是“取出法”
将序列中的元素随机取出
原序列中的该元素被剔除
被取出的元素按顺序排列
依次生成新的序列
image
代码非常简单
void Fisher_Yates_Shuffle()
{
vector<int>numy_of_Fisher;
int counter=num;
for(int i=0;i<num;i++) //随机生成位点，将该位点的元素拿出，重新生成以数组长度为范围的随机数，一直循环下去。
{
int N=rand()%counter;
numy_of_Fisher.push_back(numy[N]);
numy.erase(numy.begin()+N);
counter--;
}
for(int i=0;i<num;i++)
{
cout<<numy_of_Fisher[i]<<" ";
}
cout<<endl;
}
2.Knuth_Durstenfeld_Shuffle算法
“倒序交换法”
跟我之前的想法有些类似
所谓倒序就是从最后一个位点开始
随机生成除最后一位的位点
交换最后一个位点和生成位点的元素
接着固定最后一位不变
随机生成倒数第二位之前的位点
交换倒数第二位点和生成位点元素
直到遍历完所有元素
image
代码：
void Knuth_Durstenfeld_Shuffle()
{
int counter=num;
for(int i=num;i>0;--i)
{
int N=rand()%i;
swap(numy[N],numy[i-1]);
}
for(int i=0;i<num;i++)
{
cout<<numy[i]<<" ";
}
cout<<endl;
}
3.Inside_Out_Algorithm
“内部交换法”
与第二种方法遍历顺序相反
该方法正序遍历元素
image
代码：
void Inside_Out_Algorithm()
{
vector<int> numy_of_Inside;
numy_of_Inside.assign(numy.size(),0);
copy(numy.begin(),numy.end(),numy_of_Inside.begin());
int k;
for(int i=0;i<num;i++)
{
k=rand()%(i+1);
numy_of_Inside[i]=numy_of_Inside[k];
numy_of_Inside[k]=numy[i];
}
for(int i=0;i<num;i++)
{
cout<<numy_of_Inside[i]<<" ";
}
cout<<endl;
}
其实对比完这三种算法之后
发现原理都大同小异
甚至觉得
都没我设计的XJB操作来的简单直接
简单归简单，一用就完蛋
完整代码请移步后台留言
image
