关于洗牌
首先，什么是洗牌？百度百科上的释义为：把牌搀和整理，以便继续玩。
那么，从程序的角度，我们来思考一个问题：
如何设计一个公平的洗牌算法？
简单的洗牌算法
洗牌，显然是一个随机算法。随机还不简单？随机呗。把所有牌（所有数）放到一个数组中，每次取两张牌交换位置，随机 k 次即可。
#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;
void Shuffe(int *a, int n, int k)
{
srand((unsigned)time(NULL));
for (int i = 0; i < k; i++)
{
swap(&a[rand() % n], &a[rand() % n]);
}
}
来自HR的质疑
于是你将这段代码写给HR，认为这么简单的问题难不倒。但通常HR会进一步问：k 应该取多少？10的3次方？4次方？5次方？
很显然，取一个固定的值不合理。如果数组中有 1000000 个元素，随机 100 次太少；如果数组中只有 10 个元素，随机 10000 次又太多。一个合理的选择是，随机次数和数组中元素大小相关。比如数组有多少个元素，我们就随机多少次。
这个答案已经好很多了。但其实，连这个问题的本质都没有触及到。此时，HR一定会狡黠地一笑：这个算法公平吗？
回到问题：如何设计一个公平的洗牌算法？
公平但复杂的洗牌算法
公平——保证随机性。
其实当你开始思考这个问题时，答案不难想到。洗牌的结果是所有元素的一个排列。一副牌如果有 n 个元素，最终排列的可能性一共有 n! 个。公平的洗牌算法，应该能等概率地给出这 n! 个结果中的任意一个。
如思考到这一点，我们就能设计出一个简单的暴力算法了：对于 n 个元素，生成这 n 个元素的全排列，然后，随机抽一个。
时间复杂度
这个算法绝对是公平的。但问题是，复杂度太高！复杂度是多少呢？O(n!)。因为，n 个元素一共有 n! 种排列，我们求出所有 n! 种排列，至少需要 n! 的时间。
如果你认为这并不是什么大的复杂度，那你就错了。实际上，这是一个比指数级 O(2^n) 更高的复杂度。因为当 n>=4 开始，n! 以极快的的速度超越 2^n。
O(2^n) 已经被称为指数爆炸了，O(n!) 不可想象。
所以，这个算法确实是公平的，但是，时间不可容忍。
Knuth 洗牌算法
换个角度
我们再换一个角度思考「公平」这个话题。其实，我们也可以认为
如果：
- 一张牌出现在任何位置的概率是相等的
- 一个位置出现任何牌的概率是相等的
那么，我们可以认为他的随机性是可以保证的。
这个定义和上面的最终洗牌结果，可以等概率地给出这 n! 个排列中的任意一个，是等价的。
流程
- 该算法类似于插入排序
- 从数组的最后一个数（下标为i）开始，进行随机取余（除数为i+1,确保下标不过界）
- 将得到的下标对应的元素和最后一个数交换
- 将最后一个数不在视为数组中的元素，继续循环
- 直到只剩下第一个元素为止
这个算法就是大名鼎鼎的 Knuth-Shuffle，即 Knuth 洗牌算法。
证明
- 很明显任何一张牌出现在第一个位置的概率都是相等的。P=1/N
那任何一张牌出现在第二张的概率如何计算呢？首先该张牌不能出现在第一张，P=（N-1）/N;
而后需要从N-1张牌中被选中，概率 P=((N-1)/N)*(1/(N-1))=1/N
以此类推可以知道，任何一张牌出现在任何位置的概率是相等的。条件1证明完毕。 - 同样的道理
位置1出现任何牌的概率是1/N
位置2出现任何牌的概率同样也是((N-1)/N)*(1/(N-1))=1/N - 以此类推，任何一张牌出现在任何位置的概率是相等的
条件2证明完毕。
Knuth 何许人也？
中文名：高纳德。算法理论的创始人。我们现在所使用的各种算法复杂度分析的符号，就是他发明的。上世纪 60-70 年代计算机算法的黄金时期，近乎就是他一手主导的。他所写的《The Art of Computer Programming》，简称 TAOCP。这套书准备写七卷本，然后，到今天还没有写完，但已经被《科学美国人》评为可以媲美相对论的巨著。
比尔盖茨曾今说过，如果你看完了这套书的第一卷本，请直接给我发简历。
其他详细信息，可以自行Google。
代码
基于这个定义，我们就可以给出代码了。
#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;
int n,a[]={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15};
void Print(void)
{
for (int i=0;i<n;i++) cout<<a[i]<<' ';
cout<<endl;
}
void swap(int *a,int *b)
{
int c; c=*a; *a=*b; *b=c;
}
void Shuffe(void)
{
srand((unsigned)time(NULL));
for (int i = n - 1; i > 0; --i)
swap(&a[i], &a[rand() % i]);
}
int main(void)
{
n=sizeof(a)/sizeof(int);
while (1)
{
Shuffe();
Print();
system("pause>nul");
}
return 0;
}
核心代码只有两行，非常简洁。
应用
这个算法除了洗牌，还能怎么用？
其实，在很多随机的地方，都能使用。比如，扫雷生成随机的盘面。我们可以把扫雷的二维盘面先逐行连接，看作是一维的。之后，把 k 颗雷依次放在开始的位置。
然后，我们运行一遍 Knuth 洗牌算法，就可以随机摆放地雷了~
算法就像这世界一样，尽管复杂，但如此优雅。
Comments | NOTHING