几乎所有的程序员都写过类似于“洗牌”的算法，也就是将一个数组随机打乱后输出，虽然很简单，但是深入研究起来，这个小小的算法也是大有讲究。我在面试程序员的时候，就会经常让他们当场写一个洗牌的函数，从中可以观察到他们对于这个问题的理解和写程序的基本功。
在深入讨论之前，必须先定义出一个基本概念：究竟洗牌算法的本质是什么？也就是说，什么样的洗牌结果是“正确”的？
云风曾经有一篇博文，专门讨论了这个问题，他也给出了一个比较确切的定义，在经过洗牌函数后，如果能够保证每一个数据出现在所有位置的概率是相等的，那么这种算法是符合要求的。在这个前提下，尽量降低时间复杂度和空间复杂度就能得到好的算法。
第一个洗牌算法：
随机抽出一张牌，检查这张牌是否被抽取过，如果已经被抽取过，则重新抽取，直到找到没被抽出过的牌，然后把这张牌放入洗好的队列中，重复该过程，直到所有的牌被抽出。
大概是比较符合大脑对于洗牌的直观思维，这个算法经常出现在我遇到的面试结果中，虽然它符合我们对于洗牌算法的基本要求，但这个算法并不好，首先它的复杂度为O(N2)，而且需要额外的内存空间保存已经被抽出的牌的索引。所以当数据量比较大时，会极大降低效率。
第二个算法：
设牌的张数为n，首先准备n个不容易碰撞的随机数，然后进行排序，通过排序可以得到一个打乱次序的序列，按照这个序列将牌打乱。
这也是一个符合要求的算法，但是同样需要额外的存储空间，在复杂度上也会取决于所采用的排序算法，所以仍然不是一个好的算法。
第三个算法：
每次随机抽出两张牌交换，重复交换一定次数次后结束
void shuffle(int* data, int length)
{
for(int i=0; i<SWAP_COUNTS; i++)
{
//Rand(min, max)返回[min, max)区间内的随机数
int index1 = Rand(0, length);
int index2 = Rand(0, length);
std::swap(data[index1], data[index2]);
}
}
这又是一个常见的洗牌方法，比较有意思的问题是其中的“交换次数”，我们该如何确定一个合适的交换次数？简单的计算，交换m次后，具体某张牌始终没有被抽到的概率为((n-2)/n)^m，如果我们要求这个概率小于1/1000,那么 m>-3*ln(10)/ln(1-2/n),对于52张牌，这个数大约是176次，需要注意的是，这是满足“具体某张牌”始终没有被抽到的概率，如果需要满足“任意一张牌”没被抽到的概率小于1/1000，需要的次数还要大一些，但这个概率计算起来比较复杂，有兴趣的朋友可以试一下。
Update: 这个概率是，推算过程可以参考这里，根据这个概率，需要交换280次才能符合要求
第四个算法：
从第一张牌开始，将每张牌和随机的一张牌进行交换
void shuffle(int* data, int length)
{
for(int i=0; i<length; i++)
{
int index = Rand(0, length);
std::swap(data[i], data[index]);
}
}
很明显，这个算法是符合我们先前的要求的，时间复杂度为O(N)，而且也不需要额外的临时空间，似乎我们找到了最优的算法，然而事实并非如此，看下一个算法。
第五个算法：
void shuffle(int* data, int length)
{
for(int i=1; i<length; i++)
{
int index = Rand(0, i);
std::swap(data[i], data[index]);
}
}
一个有意思的情况出现了，这个算法和第三种算法非常相似，从直觉来说，似乎使数据“杂乱”的能力还要弱于第三种，但事实上，这种算法要强于第三种。要想严格的证明这一点并不容易，需要一些数学功底，有兴趣的朋友可以参照一下这篇论文，或者matrix67大牛的博文，也可以这样简单理解一下，对于n张牌的数据，实际排列的可能情况为n! 种，但第四种算法能够产生n^n种排列，远远大于实际的排列情况，而且n^n不能被n!整除，所以经过算法四所定义的牌与牌之间的交换程序，很可能一张牌被换来换去又被换回到原来的位置，所以这个算法不是最优的。而算法五输出的可能组合恰好是n!种，所以这个算法才是完美的。
事情并没有结束，如果真的要找一个最优的算法，还是请出最终的冠军吧！
第六个算法：
void shuffle(int* data, int length)
{
std::random_shuffle(data, data+length);
}
没错，用c++的标准库函数才是最优方案，事实上，std::random_shuffle在实现上也是采取了第四种方法，看来还是那句话，“不要重复制造轮子”
不想写 - -
在深入讨论之前，必须先定义出一个基本概念：究竟洗牌算法的本质是什么？也就是说，什么样的洗牌结果是“正确”的？
云风曾经有一篇博文，专门讨论了这个问题，他也给出了一个比较确切的定义，在经过洗牌函数后，如果能够保证每一个数据出现在所有位置的概率是相等的，那么这种算法是符合要求的。在这个前提下，尽量降低时间复杂度和空间复杂度就能得到好的算法。
第一个洗牌算法：
随机抽出一张牌，检查这张牌是否被抽取过，如果已经被抽取过，则重新抽取，直到找到没被抽出过的牌，然后把这张牌放入洗好的队列中，重复该过程，直到所有的牌被抽出。
大概是比较符合大脑对于洗牌的直观思维，这个算法经常出现在我遇到的面试结果中，虽然它符合我们对于洗牌算法的基本要求，但这个算法并不好，首先它的复杂度为O(N2)，而且需要额外的内存空间保存已经被抽出的牌的索引。所以当数据量比较大时，会极大降低效率。
第二个算法：
设牌的张数为n，首先准备n个不容易碰撞的随机数，然后进行排序，通过排序可以得到一个打乱次序的序列，按照这个序列将牌打乱。
这也是一个符合要求的算法，但是同样需要额外的存储空间，在复杂度上也会取决于所采用的排序算法，所以仍然不是一个好的算法。
第三个算法：
每次随机抽出两张牌交换，重复交换一定次数次后结束
void shuffle(int* data, int length)
{
for(int i=0; i<SWAP_COUNTS; i++)
{
//Rand(min, max)返回[min, max)区间内的随机数
int index1 = Rand(0, length);
int index2 = Rand(0, length);
std::swap(data[index1], data[index2]);
}
}
这又是一个常见的洗牌方法，比较有意思的问题是其中的“交换次数”，我们该如何确定一个合适的交换次数？简单的计算，交换m次后，具体某张牌始终没有被抽到的概率为((n-2)/n)^m，如果我们要求这个概率小于1/1000,那么 m>-3*ln(10)/ln(1-2/n),对于52张牌，这个数大约是176次，需要注意的是，这是满足“具体某张牌”始终没有被抽到的概率，如果需要满足“任意一张牌”没被抽到的概率小于1/1000，需要的次数还要大一些，但这个概率计算起来比较复杂，有兴趣的朋友可以试一下。
Update: 这个概率是，推算过程可以参考这里，根据这个概率，需要交换280次才能符合要求
第四个算法：
从第一张牌开始，将每张牌和随机的一张牌进行交换
void shuffle(int* data, int length)
{
for(int i=0; i<length; i++)
{
int index = Rand(0, length);
std::swap(data[i], data[index]);
}
}
很明显，这个算法是符合我们先前的要求的，时间复杂度为O(N)，而且也不需要额外的临时空间，似乎我们找到了最优的算法，然而事实并非如此，看下一个算法。
第五个算法：
void shuffle(int* data, int length)
{
for(int i=1; i<length; i++)
{
int index = Rand(0, i);
std::swap(data[i], data[index]);
}
}
一个有意思的情况出现了，这个算法和第三种算法非常相似，从直觉来说，似乎使数据“杂乱”的能力还要弱于第三种，但事实上，这种算法要强于第三种。要想严格的证明这一点并不容易，需要一些数学功底，有兴趣的朋友可以参照一下这篇论文，或者matrix67大牛的博文，也可以这样简单理解一下，对于n张牌的数据，实际排列的可能情况为n! 种，但第四种算法能够产生n^n种排列，远远大于实际的排列情况，而且n^n不能被n!整除，所以经过算法四所定义的牌与牌之间的交换程序，很可能一张牌被换来换去又被换回到原来的位置，所以这个算法不是最优的。而算法五输出的可能组合恰好是n!种，所以这个算法才是完美的。
事情并没有结束，如果真的要找一个最优的算法，还是请出最终的冠军吧！
第六个算法：
void shuffle(int* data, int length)
{
std::random_shuffle(data, data+length);
}
没错，用c++的标准库函数才是最优方案，事实上，std::random_shuffle在实现上也是采取了第四种方法，看来还是那句话，“不要重复制造轮子”
不想写 - -
温馨提示：内容为网友见解，仅供参考
第1个回答 2012-06-14
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define N 10
#define M 4
#define INVALID -1
void xi(int A[N], int nplayer, int player[M][N])
{
int i, j, k;
int n = N;
int tmp;
if(nplayer < 2) return;
if(nplayer > M) return;
for(i = 0; i < nplayer; i ++) {
for(j = 0; j < N; j ++) player[i][j] = INVALID;
}
j = 0;
while(n > 0){
for(i = 0; i < nplayer; i ++){
k = rand()%n;
player[i][j] = A[k];
tmp = A[n-1];
A[n-1] = A[k];
A[k] = tmp;
n--;
if(n == 0) break; //not divided
}
j++;
}
}
void show(int nplayer, int player[M][N])
{
int i, j;
if(nplayer > M) return ;
for(i = 0; i < nplayer; i ++){
printf("player %d: ", i);
for(j = 0; j < N; j++){
if(player[i][j] == INVALID) break;
printf(" %d", player[i][j]);
}
printf("\n");
}
printf("\n");
}
int main()
{
int A[N]={1,2,3,4,1,6,7,8,9,0};
int player[M][N];
srand(time(NULL));
xi(A, 2, player);
show(2, player);
xi(A, 3, player);
show(3, player);
xi(A, 4, player);
show(4, player);
return 0;
}
#include <stdlib.h>
#include <time.h>
#define N 10
#define M 4
#define INVALID -1
void xi(int A[N], int nplayer, int player[M][N])
{
int i, j, k;
int n = N;
int tmp;
if(nplayer < 2) return;
if(nplayer > M) return;
for(i = 0; i < nplayer; i ++) {
for(j = 0; j < N; j ++) player[i][j] = INVALID;
}
j = 0;
while(n > 0){
for(i = 0; i < nplayer; i ++){
k = rand()%n;
player[i][j] = A[k];
tmp = A[n-1];
A[n-1] = A[k];
A[k] = tmp;
n--;
if(n == 0) break; //not divided
}
j++;
}
}
void show(int nplayer, int player[M][N])
{
int i, j;
if(nplayer > M) return ;
for(i = 0; i < nplayer; i ++){
printf("player %d: ", i);
for(j = 0; j < N; j++){
if(player[i][j] == INVALID) break;
printf(" %d", player[i][j]);
}
printf("\n");
}
printf("\n");
}
int main()
{
int A[N]={1,2,3,4,1,6,7,8,9,0};
int player[M][N];
srand(time(NULL));
xi(A, 2, player);
show(2, player);
xi(A, 3, player);
show(3, player);
xi(A, 4, player);
show(4, player);
return 0;
}
第2个回答 2012-06-15
我也是学习“十步天下”算法写的如下代码，希望对你有帮助！
#include <iomanip.h>//与#include <iostream>有定义的冲突，这里是为stew()函数提供头文件
//#include <iostream>
#include <time.h>
#include <algorithm>
using namespace std;
#define NUM 52
void reset(int* data,int N)
{
for (int i=0;i<N;i++)
{
data[i]=i+1;
}
}
void prn(int* data,int N)
{
for (int i=0;i<N;)
{
cout<<setw(3)<<data[i++]<<" ";
if (i%10==0)
{
cout<<endl;
}
}
cout<<endl;
}
int SWAP_COUNTS=140;//洗牌次数，越大其排序越乱
void shuffle3(int* data, int length)
{
for(int i=0; i<SWAP_COUNTS; i++)
{
//Rand(min, max)返回[min, max)区间内的随机数
int index1 = rand()%length;
int index2 = rand()%length;
std::swap(data[index1], data[index2]);
}
}
void shuffle2(int* data, int length)
{
for(int i=1; i<length; i++)
{
int index = rand()%i;
std::swap(data[i], data[index]);
}
}
void shuffle1(int* data, int length)
{
std::random_shuffle(data, data+length);
}
void main()
{
int Data[NUM];
//算法一
cout<<"算法一："<<endl;
reset(Data,NUM);
for (int i=0;i<NUM;i++)
{
shuffle1(Data,i);
}
prn(Data,NUM);
//算法二
cout<<"算法二："<<endl;
reset(Data,NUM);
shuffle2(Data,NUM);
prn(Data,NUM);
//算法三
cout<<"算法三："<<endl;
reset(Data,NUM);
shuffle3(Data,NUM);
prn(Data,NUM);
//此为算法三的牌分发，可改变上面三种的顺序，这里为最后一个算法的排序分发的
const NUMBER=4;//分牌的人数
const number=NUM/NUMBER;//每个人的牌的张数
int shuffle[NUMBER][number];
for (int j=0;j<NUMBER;j++)
{
for (i=0;i<number;i++)
{
shuffle[j][i]=Data[i*NUMBER+j];
}
}
for (j=0;j<NUMBER;j++)
{
cout<<"第"<<j+1<<"人的牌为："<<endl;
for (i=0;i<number;i++)
{
cout<<setw(5)<<shuffle[j][i];
}
cout<<endl;
}
}
#include <iomanip.h>//与#include <iostream>有定义的冲突，这里是为stew()函数提供头文件
//#include <iostream>
#include <time.h>
#include <algorithm>
using namespace std;
#define NUM 52
void reset(int* data,int N)
{
for (int i=0;i<N;i++)
{
data[i]=i+1;
}
}
void prn(int* data,int N)
{
for (int i=0;i<N;)
{
cout<<setw(3)<<data[i++]<<" ";
if (i%10==0)
{
cout<<endl;
}
}
cout<<endl;
}
int SWAP_COUNTS=140;//洗牌次数，越大其排序越乱
void shuffle3(int* data, int length)
{
for(int i=0; i<SWAP_COUNTS; i++)
{
//Rand(min, max)返回[min, max)区间内的随机数
int index1 = rand()%length;
int index2 = rand()%length;
std::swap(data[index1], data[index2]);
}
}
void shuffle2(int* data, int length)
{
for(int i=1; i<length; i++)
{
int index = rand()%i;
std::swap(data[i], data[index]);
}
}
void shuffle1(int* data, int length)
{
std::random_shuffle(data, data+length);
}
void main()
{
int Data[NUM];
//算法一
cout<<"算法一："<<endl;
reset(Data,NUM);
for (int i=0;i<NUM;i++)
{
shuffle1(Data,i);
}
prn(Data,NUM);
//算法二
cout<<"算法二："<<endl;
reset(Data,NUM);
shuffle2(Data,NUM);
prn(Data,NUM);
//算法三
cout<<"算法三："<<endl;
reset(Data,NUM);
shuffle3(Data,NUM);
prn(Data,NUM);
//此为算法三的牌分发，可改变上面三种的顺序，这里为最后一个算法的排序分发的
const NUMBER=4;//分牌的人数
const number=NUM/NUMBER;//每个人的牌的张数
int shuffle[NUMBER][number];
for (int j=0;j<NUMBER;j++)
{
for (i=0;i<number;i++)
{
shuffle[j][i]=Data[i*NUMBER+j];
}
}
for (j=0;j<NUMBER;j++)
{
cout<<"第"<<j+1<<"人的牌为："<<endl;
for (i=0;i<number;i++)
{
cout<<setw(5)<<shuffle[j][i];
}
cout<<endl;
}
}
相似回答
