这个算法的应用，比如洗牌，这个大家都非常熟悉。很久以前用的是最原始的方法，就是一直rand()未出现的牌，直至生成所有的牌。这当然是一个while(1)循环，很烂的算法吧。后面听说直接交换牌，打乱即可了。但是打乱后生成的排列是随机的么，是等可能随机的么。
其实，这个问题上算法导论上早已经有了答案了，看过算法导论之后觉得没看之前真的是算法修养太差了。
算法的伪代码如下图所示：
![]()
具体c++实现如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
| #include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <time.h>
void Swap(int& nOne, int& nTwo)
{
int nTemp;
nTemp = nOne;
nOne = nTwo;
nTwo = nTemp;
}
int Random(int nBeg, int nEnd)
{
assert(nEnd >= nBeg);
if (nBeg == nEnd)
{
return nBeg;
}
else
{
return rand() % (nEnd – nBeg + 1) + nBeg;
}
}
void RandomizeInPlace(int* pnA, int nLen)
{
static bool s_bFirst = false;
if (!s_bFirst)
{
srand(time(NULL));
s_bFirst = true;
}
for (int i = 0; i < nLen; ++i)
{
Swap(pnA[i], pnA[Random(i, nLen - 1)]);
}
}
int main()
{
int nArray[20];
int i, j;
for (i = 1; i <= 20; ++i)
{
int nCnt = i;
while (nCnt–)
{
for (j = 0; j < i; ++j)
{
nArray[j] = j;
}
RandomizeInPlace(nArray, i);
for (j = 0; j < i; ++j)
{
printf("%d", nArray[j]);
}
printf("\n");
}
printf("\n");
}
return 0;
}
|
运行效果图片如下：
![]()
根据运行结果大致就可以感觉到，生成的排列都是随机的。
这里要多说一句那就是我注释的那个交换函数其实是有bug的，也许这才是不提倡使用这个交换方法的真正原因，而不仅仅是难以理解。用同一个变量去调用该函数，会将该变量置0，而不是保持原来的值！！！至于如何证明这个算法生成的均匀随机的排列，可以参考算法导论5.3节最后一部分。
证明的大致思路是利用循环不变式的证明方法：证明i次循环后得到某个排列的概论是(n -i)! / n!，那么n次循环后得到最终那个排列的
概论就是1/n!，这样就证明了该算法能够得到均匀随机排列。
这个算法其实就是随机化算法的一种，其实快排也有所谓的随机化版本，改动的地方只是随机选择了中轴元素而已，这个在算法导论上也有介绍。
