常见算法错误之随机洗牌算法
比如，我们写一个生成包含 1 - 52 这些数字的数组，要求位置是打乱的，并且不允许有数字没出现，或者有数字重复出现为了达到这个目标，典型的洗牌算法是，先生成一个 1 - 52 有序的数组，然后，做若干次交换操作，这样打乱效率较高，并且不会有数字重复的问题
于是，有人会写如下类似的代码（以下请看成伪代码）：
#define SWAP(a, b, _t) do{_t t = a; a = b; b = t; }while(0)
void shuffle(int* arr, int len)
{
int n;
for (n = 0; n < len; ++n)
{
int i = myrand(len); //生成一个 0 至 len-1之间的随机数，也可能写成 rand() % len
SWAP(arr[n], arr[i], int); //交换arr[n]和arr[i]
}
}
运行时，看起来效果也不错，这也是最为常见的写法，
即每次生成一个 0 至 len-1之间的随机数i，和原数组里依次每个数交换，保证每个数都交换了至少一次
如此广为流传的写法，殊不知，却是错的！尽管应用时看起来似乎没有什么问题
以下是算法分析：
在这里，一共做了len次交换，每一次随机范围大小都是len，那么一共产生的可能总数是pow(n,n)，即n的n次方
不过，len个数的全排列，是n!次，而pow(n,n)远比n!要大
而素数定理里，任意的n与2n之间至少存在一个素数，那么同理，n与n/2之间至少存在一个素数，并且这个素数是不能整除n的
所以，n!至少含有一个质因数，是pow(n, n)所不包含的，所以pow(n, n)绝不可能是n!的整数倍
所以，pow(n, n)所产生的组合，概率一定是不完全均等的，有一些排列出现概率高，有一些概率低，
所以，这种办法生成的排列，概率是不均匀分布的
为了更直观地说明问题，我用三个数1,2,3的排列，用此算法打乱，看看各种排列出现的次数：
随机值 最后结果排列（字母表示排列类型）
0 0 0 3 1 2 e
0 0 1 2 3 1 d
0 0 2 2 1 3 c
0 1 0 3 2 1 f
0 1 1 1 3 2 b
0 1 2 1 2 3 a
0 2 0 2 3 1 d
0 2 1 1 2 3 a
0 2 2 1 3 2 b
1 0 0 3 2 1 f
1 0 1 1 3 2 b
1 0 2 1 2 3 a
1 1 0 3 1 2 e
1 1 1 2 3 1 d
1 1 2 2 1 3 c
1 2 0 1 3 2 b
1 2 1 2 1 3 c
1 2 2 2 3 1 d
2 0 0 1 3 2 b
2 0 1 2 1 3 c
2 0 2 2 3 1 d
2 1 0 1 2 3 a
2 1 1 3 1 2 e
2 1 2 3 2 1 f
2 2 0 2 1 3 c
2 2 1 3 2 1 f
2 2 2 3 1 2 e
统计一下：
1 2 3 : 4
1 3 2 : 5
2 1 3 : 5
2 3 1 : 5
3 1 2 : 4
3 2 1 : 4
总排列数是6，而27种生成结果是无论如何也不可能平均下去的
其中，随机值是指myrand(len)的返回值，每次生成调用了三次，就有三个值
数据中，清晰可见，每种排列出现次数并不一样，而且，如果长度不止3，那么这种情况会更为严重，
次数差别会更大，更不均匀
在证明了这个算法是不对的以后，那正确的应该怎么写呢？
并不复杂，记住以下的代码吧：
#define SWAP(a, b, _t) do{_t t = a; a = b; b = t; }while(0)
void shuffle(int* arr, int len)
{
int n;
for (n = len; n > 1; --n)
{
int i = myrand(n);
SWAP(arr[n - 1], arr[i], int);
}
}
完.
我来学习加接分。。。
