本來打算寫24點的程序，以體現(xiàn)C++對算法表達的清晰性。但在此之前，得先解決一個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)了遞歸，有點費解，好比多模板偏特化中又出現(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)年，我讀懂了這段代碼之后，馬上對遞歸的理解有了更深刻的認識。
但是，這段代碼中存在著一個非常丑陋的缺陷，其輸出夾雜在操作之中，假如每一個排列的結(jié)果不是要顯示在控制臺上，而是要寫入文本，或者是顯示在窗口上，那么就必須修改這個完美遞歸的排列函數(shù)，這無疑很不完美。當(dāng)然解決之法也不是沒有，使用函數(shù)對象，C中就只能用回調(diào)函數(shù)，將其作為參數(shù)傳入permutate中，每一次遞歸完成，就祭出函數(shù)對象輸出排列的結(jié)果。Windows API中的很多枚舉函數(shù)，例如EnumFont，EnumWindows都用了這法子。但我對這個法子很不感冒，它太不可控了；其次，還有另外一個問題，就是Swap中，假如對象很大，每一次交換則將耗費多少CPU資源，而permutate中，基本上是都是在Swap來Swap去；最后也是最大問題，這種方法只可用于全排列，對于部分排列，比如，求P(5,2)，它完全無能為力，因此，必須另尋出路。
……
上面省略了思考的過程，請恕我直接給出解決方案，其實很簡單。
先從最簡單的排列對象開始考慮，即從0到N的排列數(shù)，只要搞定了它的排列方式，就可以搞定所有對象的排列了，WHY？因為0到N可作為數(shù)組的索引，可能對這個答案有點迷糊，不要緊，繼續(xù)看下去。考察我們偉大的大腦是如何做排列的，請動筆，寫下4！的全部排列，看能否從中得到什么啟發(fā)。
0123， 0132， 0213， 0231， 0312， 0321， 1023， 1032， …… ，3201，3210。終于寫完了0到3的全部全排列，手都酸了。可以發(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呢，這里面隱藏著什么奧秘嗎？仔細對比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的話，我也不知道代碼會是什么樣子，起碼不會這么易于表達，除了設(shè)計好算法和數(shù)據(jù)結(jié)構(gòu)，還必須多花些心思琢磨代碼的設(shè)計，這不是一件快樂的事情，而用C++寫代碼，則非常愜意。
C++是我最喜歡的語言，它集自由、博大、復(fù)雜、簡約、高效于一身，又能很好地均衡這些特點，使它們和平共處，將“不為用到的任何特性付出一點點代價”的宗旨貫徹到底，其他的任何一種語言的都不具備像C++這樣的內(nèi)涵，使用C++之時，直有C++在手，江山我有的感覺。C雖然能讓你掌管一切，但用C開發(fā)，有如戴著鐐銬在跳舞，無時不刻要小心翼翼地人肉管理一切細節(jié)，實在太累了。而用C#、JAVA等其他語言時，雖然養(yǎng)尊處優(yōu)，但想走不尋常路之時，又處處受限制，很有點寄人籬下的味道，未免不痛快。只有C++，既能下，又能上，進可攻，退可守，想怎么樣就怎么樣，盡情地飛翔。只要你愿意，你就可以在這一片世界里隨心所欲地發(fā)揮你的一切聰明才智，創(chuàng)造出種種奇技淫巧，而不會受到一點點約束。問題來了，自由得過頭了，就失去了控制，自由未必是好事。好多人，自由得甚至忘記了他要用C++的根本目的是什么，于是，C++到了他的手里，就變成為自由而自由，為復(fù)雜而復(fù)雜的利器，不但用它來折磨自己，還用它來迷惑別人，以致于忽視了原本要解決的問題，這樣一來，問題就很嚴重了。好的工具本來就是要用來做點實事的，做不了實事，要拿什么來證明自己呢？
對于C++，沒什么好說的。但C++的教育，就有太多的不滿，要指責(zé)之處，也實在太多了，其中最為人詬病，就是很多C++的教材，都鼓勵讀者將注意力集中到C++的細節(jié)中，而忘記了如何用C++來簡潔質(zhì)樸地來表達設(shè)計思路。關(guān)于這一點，很多達人君子也已經(jīng)一再嚴厲地批評再批評。我也不想重復(fù)他們的論調(diào)，只想舉兩個例子。
C++因缺乏GC，而廣受非議。但內(nèi)存管理，其實不值得議論再議論，只要設(shè)計編寫得當(dāng)，少耍小聰明，代碼中出現(xiàn)new和delete的次數(shù)可以很少很少，就算出現(xiàn)，也只會出現(xiàn)于底層代碼中。為了彌補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)存管理了，在那里分配，在那里釋放，都很有必要細細地斟酌一番，auto_ptr并非什么萬能丹，一有內(nèi)存分配，就搬出auto_ptr，只怕屬本本主義的作風(fēng)。即此以觀，什么share_ptr，scope_ptr，也就那么一點點作用而已，無須大書特書。
我承認，BOOST精妙無比，那都是C++程序聰明才智的結(jié)晶，但其實，真正搬得上臺面，發(fā)揮大作用的玩意，為數(shù)并不多，好比Tuple，可以方便地返回函數(shù)中的多個結(jié)果，例如……（請大家自己動手，或baidu或google），乍聽起來，似乎美妙無比。但其實，沒什么作用，什么時候，我們需要從函數(shù)中返回多個值？需要從函數(shù)中返回多值時，我會盡量地寫本地代碼，實在必須調(diào)用函數(shù)了，只好搬出指針或引用，將參數(shù)傳遞進去，如果數(shù)量太多了，那就動用結(jié)構(gòu)，用結(jié)構(gòu)組織這些返回值，這一切，做起來，并沒什么太大的不便。但是如果動用Tuple返回多個結(jié)果，可能方便了那么一點點，卻將導(dǎo)致代碼難以維護，因為Tuple里面的值各表示了什么意思，無法直接從代碼中看得出來，用過Tuple的同學(xué)自然知道我要說什么。Tuple的實現(xiàn)非常巧妙，如此費盡心思弄出來的東西，不過是一只漂亮花瓶而已，真讓人扼腕嘆息不已，很多C++的庫，尤其是BOOST，都是這個樣子，看起來很精致，用起來，卻完全不是那么一回事，而且還引入很多不必要復(fù)雜性，世人稱心智包袱。
……
用C++做設(shè)計，很容易就導(dǎo)致庫設(shè)計，如果設(shè)計出來的庫有用好用，那也罷了，問題是費了九牛二虎之力，搞出來的東西，半點得不到別人的認可，甚至連自己都無法認可，那就太不應(yīng)該了。
用C++寫代碼，老老實實地寫代碼，不要忘記了編程的用意，別沉浸于語言中，盡量將代碼寫得直白易懂，少賣弄聰明才智， 慎用C++的一切特性，繼承、虛函數(shù)、操作符重載、模板、異常、new delete、……，更加不要用它們創(chuàng)造出什么奇技淫巧，必須用它們的時候，必須要有使用它們的理由。確實存在必須使用它們的理由，還堅決不用，那就是傻瓜和偏執(zhí)狂了，這不是合格的C++碼農(nóng)，C++雖然不喜歡胡作非為的搗蛋鬼，但也杜絕一切墨守成規(guī)的書呆子。