本來打算寫24點的程序,以體現(xiàn)C++對算法表達(dá)的清晰性。但在此之前,得先解決一個N個數(shù)中取兩個數(shù)的組合問題,也即C(N,2),于是想到干脆連排列也一塊搞定,而且在討論全排列的時候,還牽扯到一個有趣的代碼問題,因此,就這樣專用一文來論排列與組合,內(nèi)容還相當(dāng)翔實。但是寫完全排列的時候,發(fā)現(xiàn)文章已經(jīng)很長了,只好打住,留待下期再論組合與部分排列。
先來看一段有名代碼,稍作了改動,它出自于國外的算法書中,在國內(nèi)的算法書中到處可以看到它的身影,代碼本身確實非常巧妙,但其實,存在很大的問題。
template<typename T>
void Perm(T* pT, int n, int m)


{
if (n == m)

{
for (int i=0; i<m; i++)
cout << pT[i] << " ";
cout << endl;
return;
}
else

{
for (int i=m; i<n; i++)

{
swap(pT[m], pT[i]);
Perm(pT, n, m+1);
swap(pT[m], pT[i]);
}
}
} 循環(huán)中出現(xiàn)了遞歸,有點費(fèi)解,好比多模板偏特化中又出現(xiàn)了多繼承還夾雜著虛函數(shù),但在這里,還是很好理解的,代碼按乘法原理來構(gòu)造,這也是排列算法的由來。計算N個數(shù)的全排列,就是針對內(nèi)中的任一個數(shù)實行一次N-1個數(shù)的全排列,即N!= N * (N-1)!。循環(huán)就是為了讓數(shù)組中的每個元素都參與到排列中來。首先取出第0個數(shù),對行實行了(N-1)!。然后取出第1個數(shù),其實就是將第1個數(shù)放到第0位中,第0個數(shù)放到第1個數(shù)中,通過Swap函數(shù),實行一次(N-1)!,之后,第1、0個再各就各位,返回原位。計算(N-1)!的時候,也按照N!那樣,對N-1個數(shù)的任一個數(shù)實行(N-2)!。完美的遞歸出現(xiàn)了,既然有遞歸,就有結(jié)束遞歸的代碼,遞歸結(jié)束在0!,也即是m==n時,表示已經(jīng)完成了一個排列。由于是循環(huán)中出現(xiàn)遞歸,遞歸中又出現(xiàn)了循環(huán),因此就算遞歸完成了,代碼還要繼續(xù)遞歸,遞歸到遞歸中的循環(huán)都結(jié)束了。當(dāng)年,我讀懂了這段代碼之后,馬上對遞歸的理解有了更深刻的認(rèn)識。
但是,這段代碼中存在著一個非常丑陋的缺陷,其輸出夾雜在操作之中,假如每一個排列的結(jié)果不是要顯示在控制臺上,而是要寫入文本,或者是顯示在窗口上,那么就必須修改這個完美遞歸的排列函數(shù),這無疑很不完美。當(dāng)然解決之法也不是沒有,使用函數(shù)對象,C中就只能用回調(diào)函數(shù),將其作為參數(shù)傳入permutate中,每一次遞歸完成,就祭出函數(shù)對象輸出排列的結(jié)果。Windows API中的很多枚舉函數(shù),例如EnumFont,EnumWindows都用了這法子。但我對這個法子很不感冒,它太不可控了;其次,還有另外一個問題,就是Swap中,假如對象很大,每一次交換則將耗費(fèi)多少CPU資源,而permutate中,基本上是都是在Swap來Swap去;最后也是最大問題,這種方法只可用于全排列,對于部分排列,比如,求P(5,2),它完全無能為力,因此,必須另尋出路。
……
上面省略了思考的過程,請恕我直接給出解決方案,其實很簡單。
先從最簡單的排列對象開始考慮,即從0到N的排列數(shù),只要搞定了它的排列方式,就可以搞定所有對象的排列了,WHY?因為0到N可作為數(shù)組的索引,可能對這個答案有點迷糊,不要緊,繼續(xù)看下去??疾煳覀儌ゴ蟮拇竽X是如何做排列的,請動筆,寫下4!的全部排列,看能否從中得到什么啟發(fā)。
0123, 0132, 0213, 0231, 0312, 0321, 1023, 1032, …… ,3201,3210。終于寫完了0到3的全部全排列,手都酸了??梢园l(fā)現(xiàn)一件事,就是按這種方式寫下來的排列,任何一個排列數(shù)的下一個排列數(shù)必定是唯一的,比如,2031的下一個就是2103,而不會是其他的排列,這就好像任何自然數(shù)N的有且必定有唯一一個后繼N+1,但是排列數(shù)就不一定都有后繼了,3210就是最后一個排列數(shù)了。于是,我們就可以像普通循環(huán)那樣寫代碼了,for(排列對象=0123; 排列對象!=3210; 排列對象.ToNext){輸出排列對象}。非常美妙吧,不過當(dāng)務(wù)之急,是先class Permutation。
class Permutation


{
public:

enum
{MAX_SIZE = 10};
Permutation(int count)

{
assert(0 < count && count < MAX_SIZE);
m_nCount = (char)count;
for (char i=0; i<m_nCount; i++)
m_Indexs[i] = i;
}

public:
bool ToNext();

char operator[] (int n)const

{
assert(0 <= n && n <= m_nCount);
return m_Indexs[n];
}

private:
char m_Indexs[MAX_SIZE];
char m_nCount;
}; 以上是初版,只支持全排列,部分排列時,它的定義又將不同。我不想再解釋它為何是這個樣子,請各位用心揣摩,一切都那么必然。我再次用了呆板的數(shù)組的定義方式,就好像八皇后那樣,因為日常中使用的排列數(shù)很少會多于10個的,這一點我很放心,各位也大可以放心。排列后的結(jié)果m_Indexs,本來也打算像八皇后那樣,直接public出來,但考慮到這個類比八皇后更加通用,而且operator[]確實有點方便使用,寫代碼時,操作符能不重載就別重載。
接下來,就要對付Permutation.DoNext,也即本文的主角。先考慮一個問題,為什么我們就知道02431的下一個排列必然是03124呢,這里面隱藏著什么奧秘嗎?仔細(xì)對比02431、03124這兩個排列的差異。發(fā)現(xiàn):02431第0位的0沒有變,但第1位的2變成了3,02431中2與3交換后,變成了03421。為什么是2呢?在02431中,1<3, 3<4, 但到了2時,則為4>2,所以2成了被指定的那個人。那為什么是3要與2交換呢,因為3后面的1<2,從后往前算,3是第一個比2大的數(shù)。所以,2與3交換,理所當(dāng)然,不可不戒。交換之后,02431變成了03421,再比較03124,就421與124不同,而且還互為逆序,OK,我們找到奧秘了。至于奧秘的理由,里面自有數(shù)學(xué)原因,但已經(jīng)無須關(guān)心了,我們的職任是編寫代碼。于是,代碼如下。代碼就不解釋了,請對照上面的描述理解代碼。
bool Permutation::ToNext()


{
char nReverse = m_nCount-1;
while (nReverse > 0 && m_Indexs[nReverse]<m_Indexs[nReverse-1])
nReverse--; // 尋找第一個要交換的元素
if (nReverse == 0) // 找不到,表示全排已經(jīng)完成
return false;

char nSwap = m_nCount - 1;
while (m_Indexs[nSwap] < m_Indexs[nReverse-1])
nSwap--; // 尋找第二個元素
swap(m_Indexs[nReverse-1], m_Indexs[nSwap]); // 開始交換
reverse(m_Indexs+nReverse, m_Indexs+m_nCount); // 逆順
return true;
}

main也不含糊,只為體現(xiàn)Permutation的用法。
int main()


{
const int N = 3;
Permutation perm(N);

const char* sTests[N] =
{"零", "一", "二"};
do

{
for (int i=0; i<N; i++)
cout << sTests[perm[i]] << " ";
cout << endl;
}while(perm.ToNext());
return 0;
}

CLASS真是好東西,如果不用C++,而用C的話,我也不知道代碼會是什么樣子,起碼不會這么易于表達(dá),除了設(shè)計好算法和數(shù)據(jù)結(jié)構(gòu),還必須多花些心思琢磨代碼的設(shè)計,這不是一件快樂的事情,而用C++寫代碼,則非常愜意。
C++是我最喜歡的語言,它集自由、博大、復(fù)雜、簡約、高效于一身,又能很好地均衡這些特點,使它們和平共處,將“不為用到的任何特性付出一點點代價”的宗旨貫徹到底,其他的任何一種語言的都不具備像C++這樣的內(nèi)涵,使用C++之時,直有C++在手,江山我有的感覺。C雖然能讓你掌管一切,但用C開發(fā),有如戴著鐐銬在跳舞,無時不刻要小心翼翼地人肉管理一切細(xì)節(jié),實在太累了。而用C#、JAVA等其他語言時,雖然養(yǎng)尊處優(yōu),但想走不尋常路之時,又處處受限制,很有點寄人籬下的味道,未免不痛快。只有C++,既能下,又能上,進(jìn)可攻,退可守,想怎么樣就怎么樣,盡情地飛翔。只要你愿意,你就可以在這一片世界里隨心所欲地發(fā)揮你的一切聰明才智,創(chuàng)造出種種奇技淫巧,而不會受到一點點約束。問題來了,自由得過頭了,就失去了控制,自由未必是好事。好多人,自由得甚至忘記了他要用C++的根本目的是什么,于是,C++到了他的手里,就變成為自由而自由,為復(fù)雜而復(fù)雜的利器,不但用它來折磨自己,還用它來迷惑別人,以致于忽視了原本要解決的問題,這樣一來,問題就很嚴(yán)重了。好的工具本來就是要用來做點實事的,做不了實事,要拿什么來證明自己呢?
對于C++,沒什么好說的。但C++的教育,就有太多的不滿,要指責(zé)之處,也實在太多了,其中最為人詬病,就是很多C++的教材,都鼓勵讀者將注意力集中到C++的細(xì)節(jié)中,而忘記了如何用C++來簡潔質(zhì)樸地來表達(dá)設(shè)計思路。關(guān)于這一點,很多達(dá)人君子也已經(jīng)一再嚴(yán)厲地批評再批評。我也不想重復(fù)他們的論調(diào),只想舉兩個例子。
C++因缺乏GC,而廣受非議。但內(nèi)存管理,其實不值得議論再議論,只要設(shè)計編寫得當(dāng),少耍小聰明,代碼中出現(xiàn)new和delete的次數(shù)可以很少很少,就算出現(xiàn),也只會出現(xiàn)于底層代碼中。為了彌補(bǔ)GC的缺席,C++界中發(fā)明了種種內(nèi)存管理的巧妙手法,其中最得力的一種辦法就是智能指針,而出現(xiàn)于標(biāo)準(zhǔn)庫中就是大名鼎鼎的auto_ptr了,甚至有人說,一本C++的教材,只要不介紹auto_ptr,就不屬于合格的教科書。但其實,auto_ptr并不見得那么重要,好比以下的代碼
Int* pa = new int;
……
delete pa;
這代碼確實不好,于是該auto_ptr上場表演,變成
auto_ptr<int*> pa(new int);
delete消失了,何其美妙,但其實,最樸實的代碼,連new都可以不用的,既然沒有new,就不需要auto_ptr了,最簡潔的代碼,非常簡單。
Int a = 0;
一行就好,什么都用不了,很多出現(xiàn)auto_ptr的地方,直接用局部變量就可以了。不能使用局部變量的地方,就屬復(fù)雜的內(nèi)存管理了,在那里分配,在那里釋放,都很有必要細(xì)細(xì)地斟酌一番,auto_ptr并非什么萬能丹,一有內(nèi)存分配,就搬出auto_ptr,只怕屬本本主義的作風(fēng)。即此以觀,什么share_ptr,scope_ptr,也就那么一點點作用而已,無須大書特書。
我承認(rèn),BOOST精妙無比,那都是C++程序聰明才智的結(jié)晶,但其實,真正搬得上臺面,發(fā)揮大作用的玩意,為數(shù)并不多,好比Tuple,可以方便地返回函數(shù)中的多個結(jié)果,例如……(請大家自己動手,或baidu或google),乍聽起來,似乎美妙無比。但其實,沒什么作用,什么時候,我們需要從函數(shù)中返回多個值?需要從函數(shù)中返回多值時,我會盡量地寫本地代碼,實在必須調(diào)用函數(shù)了,只好搬出指針或引用,將參數(shù)傳遞進(jìn)去,如果數(shù)量太多了,那就動用結(jié)構(gòu),用結(jié)構(gòu)組織這些返回值,這一切,做起來,并沒什么太大的不便。但是如果動用Tuple返回多個結(jié)果,可能方便了那么一點點,卻將導(dǎo)致代碼難以維護(hù),因為Tuple里面的值各表示了什么意思,無法直接從代碼中看得出來,用過Tuple的同學(xué)自然知道我要說什么。Tuple的實現(xiàn)非常巧妙,如此費(fèi)盡心思弄出來的東西,不過是一只漂亮花瓶而已,真讓人扼腕嘆息不已,很多C++的庫,尤其是BOOST,都是這個樣子,看起來很精致,用起來,卻完全不是那么一回事,而且還引入很多不必要復(fù)雜性,世人稱心智包袱。
……
用C++做設(shè)計,很容易就導(dǎo)致庫設(shè)計,如果設(shè)計出來的庫有用好用,那也罷了,問題是費(fèi)了九牛二虎之力,搞出來的東西,半點得不到別人的認(rèn)可,甚至連自己都無法認(rèn)可,那就太不應(yīng)該了。
用C++寫代碼,老老實實地寫代碼,不要忘記了編程的用意,別沉浸于語言中,盡量將代碼寫得直白易懂,少賣弄聰明才智, 慎用C++的一切特性,繼承、虛函數(shù)、操作符重載、模板、異常、new delete、……,更加不要用它們創(chuàng)造出什么奇技淫巧,必須用它們的時候,必須要有使用它們的理由。確實存在必須使用它們的理由,還堅決不用,那就是傻瓜和偏執(zhí)狂了,這不是合格的C++碼農(nóng),C++雖然不喜歡胡作非為的搗蛋鬼,但也杜絕一切墨守成規(guī)的書呆子。