這個(gè)算法的應(yīng)用，比如洗牌，這個(gè)大家都非常熟悉。很久以前用的是最原始的方法，就是一直rand()未出現(xiàn)的牌，直至生成所有的牌。
這當(dāng)然是一個(gè)while(1)循環(huán)，很爛的算法吧。后面聽說直接交換牌，打亂即可了。但是打亂后生成的排列是隨機(jī)的么，是等可能隨機(jī)的么。
其實(shí)，這個(gè)問題上算法導(dǎo)論上早已經(jīng)有了答案了，看過算法導(dǎo)論之后覺得沒看之前真的是算法修養(yǎng)太差了。
算法的偽代碼如下圖所示：
具體c++實(shí)現(xiàn)如下：
#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;
}
//返回一個(gè)在區(qū)間[nBeg, nEnd]內(nèi)的隨機(jī)數(shù)
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;
}
運(yùn)行效果圖片如下：
根據(jù)運(yùn)行結(jié)果大致就可以感覺到，生成的排列都是隨機(jī)的。
這里要多說一句那就是我注釋的那個(gè)交換函數(shù)其實(shí)是有bug的，也許這才是不提倡使用這個(gè)交換方法的真正原因，而不僅僅是
難以理解。用同一個(gè)變量去調(diào)用該函數(shù)，會(huì)將該變量置0，而不是保持原來的值！！！
至于如何證明這個(gè)算法生成的均勻隨機(jī)的排列，可以參考算法導(dǎo)論5.3節(jié)最后一部分。
證明的大致思路是利用循環(huán)不變式的證明方法：證明i次循環(huán)后得到某個(gè)排列的概論是(n -i)! / n!，那么n次循環(huán)后得到最終那個(gè)排列的
概論就是1/n!，這樣就證明了該算法能夠得到均勻隨機(jī)排列。
這個(gè)算法其實(shí)就是隨機(jī)化算法的一種，其實(shí)快排也有所謂的隨機(jī)化版本，改動(dòng)的地方只是隨機(jī)選擇了中軸元素而已，這個(gè)
在算法導(dǎo)論上也有介紹。