huaxiazhihuo

 

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
--;    // 寻找第一个要交换的元素
    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++写代码,则非常惬意。



posted on 2011-07-15 14:41 华夏之火 阅读(2393) 评论(3)  编辑 收藏 引用

评论

# re: C++代码(3)全排列 2011-07-15 16:40 kongque

写得不错,支持!  回复  更多评论   

# re: C++代码(3)全排列[未登录] 2011-07-16 08:06 chipset

next_permutation and prev_permutation in STL will suffice  回复  更多评论   

# re: C++代码(3)全排列 2011-07-16 12:02 华夏之火

@chipset
next_permutation和prev_permutation只能应对全排列,本文只是为部分排列和组合而准备的  回复  更多评论   


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


导航

统计

常用链接

留言簿(6)

随笔分类

随笔档案

搜索

积分与排名

最新评论

阅读排行榜

评论排行榜