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