本来打算写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的全部全排列，手都酸了。可以发现一件事，就是按这种方式写下来的排列，任何一个排列数的下一个排列数必定是唯一的，比如，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++写代码，则非常惬意。