本来打算写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++写代码,则非常惬意。