C++代码（3）全排列

本来打算写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--;    /

补充：软件开发 , C++ ,