本來打算寫24點的程序，以體現C++對算法表達的清晰性。但在此之前，得先解決一個N個數中取兩個數的組合問題，也即C(N,2)，于是想到干脆連排列也一塊搞定，而且在討論全排列的時候，還牽扯到一個有趣的代碼問題，因此，就這樣專用一文來論排列與組合，內容還相當翔實。但是寫完全排列的時候，發現文章已經很長了，只好打住，留待下期再論組合與部分排列。
先來看一段有名代碼，稍作了改動，它出自于國外的算法書中，在國內的算法書中到處可以看到它的身影，代碼本身確實非常巧妙，但其實，存在很大的問題。
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]);
}
}
} 循環中出現了遞歸，有點費解，好比多模板偏特化中又出現了多繼承還夾雜著虛函數，但在這里，還是很好理解的，代碼按乘法原理來構造，這也是排列算法的由來。計算N個數的全排列，就是針對內中的任一個數實行一次N-1個數的全排列，即N！= N * （N-1）！。循環就是為了讓數組中的每個元素都參與到排列中來。首先取出第0個數，對行實行了（N-1）！。然后取出第1個數，其實就是將第1個數放到第0位中，第0個數放到第1個數中，通過Swap函數，實行一次（N-1）！，之后，第1、0個再各就各位，返回原位。計算（N-1）！的時候，也按照N！那樣，對N-1個數的任一個數實行（N-2）！。完美的遞歸出現了，既然有遞歸，就有結束遞歸的代碼，遞歸結束在0！，也即是m==n時，表示已經完成了一個排列。由于是循環中出現遞歸，遞歸中又出現了循環，因此就算遞歸完成了，代碼還要繼續遞歸，遞歸到遞歸中的循環都結束了。當年，我讀懂了這段代碼之后，馬上對遞歸的理解有了更深刻的認識。
但是，這段代碼中存在著一個非常丑陋的缺陷，其輸出夾雜在操作之中，假如每一個排列的結果不是要顯示在控制臺上，而是要寫入文本，或者是顯示在窗口上，那么就必須修改這個完美遞歸的排列函數，這無疑很不完美。當然解決之法也不是沒有，使用函數對象，C中就只能用回調函數，將其作為參數傳入permutate中，每一次遞歸完成，就祭出函數對象輸出排列的結果。Windows API中的很多枚舉函數，例如EnumFont，EnumWindows都用了這法子。但我對這個法子很不感冒，它太不可控了；其次，還有另外一個問題，就是Swap中，假如對象很大，每一次交換則將耗費多少CPU資源，而permutate中，基本上是都是在Swap來Swap去；最后也是最大問題，這種方法只可用于全排列，對于部分排列，比如，求P(5,2)，它完全無能為力，因此，必須另尋出路。
……
上面省略了思考的過程，請恕我直接給出解決方案，其實很簡單。
先從最簡單的排列對象開始考慮，即從0到N的排列數，只要搞定了它的排列方式，就可以搞定所有對象的排列了，WHY？因為0到N可作為數組的索引，可能對這個答案有點迷糊，不要緊，繼續看下去。考察我們偉大的大腦是如何做排列的，請動筆，寫下4！的全部排列，看能否從中得到什么啟發。
0123， 0132， 0213， 0231， 0312， 0321， 1023， 1032， …… ，3201，3210。終于寫完了0到3的全部全排列，手都酸了?？梢园l現一件事，就是按這種方式寫下來的排列，任何一個排列數的下一個排列數必定是唯一的，比如，2031的下一個就是2103，而不會是其他的排列，這就好像任何自然數N的有且必定有唯一一個后繼N+1，但是排列數就不一定都有后繼了，3210就是最后一個排列數了。于是，我們就可以像普通循環那樣寫代碼了，for(排列對象=0123; 排列對象!=3210; 排列對象.ToNext){輸出排列對象}。非常美妙吧，不過當務之急，是先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;
}; 以上是初版，只支持全排列，部分排列時，它的定義又將不同。我不想再解釋它為何是這個樣子，請各位用心揣摩，一切都那么必然。我再次用了呆板的數組的定義方式，就好像八皇后那樣，因為日常中使用的排列數很少會多于10個的，這一點我很放心，各位也大可以放心。排列后的結果m_Indexs，本來也打算像八皇后那樣，直接public出來，但考慮到這個類比八皇后更加通用，而且operator[]確實有點方便使用，寫代碼時，操作符能不重載就別重載。
接下來，就要對付Permutation.DoNext，也即本文的主角。先考慮一個問題，為什么我們就知道02431的下一個排列必然是03124呢，這里面隱藏著什么奧秘嗎？仔細對比02431、03124這兩個排列的差異。發現：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大的數。所以，2與3交換，理所當然，不可不戒。交換之后，02431變成了03421，再比較03124，就421與124不同，而且還互為逆序，OK，我們找到奧秘了。至于奧秘的理由，里面自有數學原因，但已經無須關心了，我們的職任是編寫代碼。于是，代碼如下。代碼就不解釋了，請對照上面的描述理解代碼。
bool Permutation::ToNext()
{
char nReverse = m_nCount-1;
while (nReverse > 0 && m_Indexs[nReverse]<m_Indexs[nReverse-1])
nReverse--; // 尋找第一個要交換的元素
if (nReverse == 0) // 找不到，表示全排已經完成
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也不含糊，只為體現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的話，我也不知道代碼會是什么樣子，起碼不會這么易于表達，除了設計好算法和數據結構，還必須多花些心思琢磨代碼的設計，這不是一件快樂的事情，而用C++寫代碼，則非常愜意。