如何生成均匀随机排列(等概率生成排列)

这个算法的应用,比如洗牌,这个大家都非常熟悉。很久以前用的是最原始的方法,就是一直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)
// {
// nOne = nOne + nTwo;
// nTwo = nOne – nTwo;
// nOne = nOne – nTwo;
// }
void Swap(int& nOne, int& nTwo)
{
int nTemp;
nTemp = nOne;
nOne = nTwo;
nTwo = nTemp;
}
//返回一个在区间[nBeg, nEnd]内的随机数
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!,这样就证明了该算法能够得到均匀随机排列。
这个算法其实就是随机化算法的一种,其实快排也有所谓的随机化版本,改动的地方只是随机选择了中轴元素而已,这个在算法导论上也有介绍。