1.算法
http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle
简单的原理如下图所示:
2.原理
总结下,洗牌算法Fisher_Yates的原理就是把从1到n的顺序候选集随机打乱,
做法就是
第1次从1-n的候选集合随机选个数,拿出此数,并把它从候选集合剔除(候选集合n-1)。
第2次从1-n-1的候选集合随机选个数,拿出此数,并把它从候选集合剔除(候选集合n-2)。
第2次从1-n-2的候选集合随机选个数,拿出此数,并把它从候选集合剔除(候选集合n-3)。
以此类推。
3.理论保证
个人理解,如有错误请大家纠正:
a,b,c
第1次取出a的概率 1/3
第2次取出a的概率 2/3(取出b概率+取出c概率) * 1/2 (剩下2个中取出a的概率) = 1/3
第3次取出a的概率 2/3 * 1/2 * 1/1 = 1/3
以此类推可以算出b和c,得到如下表格:
字符/出现位置概率 | 1 | 2 | 3 |
a | 1/3 | 1/3 | 1/3 |
b | 1/3 | 1/3 | 1/3 |
c | 1/3 | 1/3 | 1/3 |
4.实际应用
有个时间复杂度是O(n)的实现,如下:
void ShuffleArray_Fisher_Yates(char* arr, int len)
{
int i = len, j;
char temp; if ( i == ) return;
while ( --i ) {
j = rand() % (i+);
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}