SmartPtr
本博客已搬至:http://www.cnblogs.com/baiyanhuang/
posts - 29,comments - 176,trackbacks - 0
By SmartPtr(http://www.cppblog.com/SmartPtr/)

给出1, 2, 3, 4四个数, 请编程输出其全排列, 如:
1 2 3 4
1 2 4 3
1 3 2 4
1 3 4 2
...
这样的题, 我们在学校的时候一般都遇到过,而我们最先能想到的,应该就是递归实现了,因为这和我们我理解的数学中的排列组合比较一致:先取第一个数,有4种可能,再在剩下的3个数种取出第二个数,这又有3种可能,这样下去直到取到最后一个数。 这样,4个数的全排列就有4*3*2 = 24个。n个数的全排列就是n*(n-1)*(n-2)*...*2*1. 按照这个描述, 我们发现有两点在程序中递归实现时十分重要:
1. 哪些数已经取过了而哪些数又是没有取过,可以用的?
2. 现在取的是哪一个数。
确保了这两个信息,我们的递归实现就没有什么问题了。对于第一个问题,我们有两种方法可以实现:
1) 用一个对应的bool型数组来记录被排列数组的使用状态,这个状态在递归过程中需要回溯
2) 用一个ILLEGAL值来表示不是属于排序的数,排列数组中的数一旦被使用,就用这个值来覆盖,当然,递归过程中此值也需要回溯。
同样,现在取得是哪个数,我们也有两种方法来表示:
1) 用参数的方式来表明这次递归调用是为了得第几个值、
2) 用一个静态变量来表示当前递归的深度,此深度值表明了我当前取的是哪个数。

上面两点的两种解决方法排列组合一下:),我们就有4种方法

首先是定义最大数组长度与非法值

#define N 10
#define ILLEAGALNUM  -100

下面列出每一种实现:

//数组存使用状态,调用深度表示取第几个数
void Permutation1(int a[], int n)
{
    
static int out[N]; // result array
    static bool m[N] = {1,1,1,1,1,1,1,1,1,1}; // mark array, indicate whether the coorespond element 
                                              
//in array a is already used.
    static int depth = -1;                      //recursive call depth.
    depth++;
    
for(int i = 0; i < n; ++i)
    {
        
if(depth == n)                      // if we already get the last num, print it
        {
            
static int l = 1;
            printf(
"%3d: ", l++);
            
for(int k = 0; k<n; k++) printf("%d "out[k]);
            printf(
" ");
            depth
--;
            
return;
        }
        
else if(true == m[i])                      // if element i not used
        {
            
out[depth] = a[i];
            m[i] 
= false;                      // mark element i as used
            Permutation1(a, n);                      // recursive to get next num
            m[i] = true;                      // backdate , so that we can try another case
        }
    }
    depth
--;
}

//修改数据数组表示其使用状态,参数表示取第几个数
void Permutation2(int a[], int index, int n)
{
    
static int out[N];
    
for(int i = 0; i < n; ++i)
    {
        
if(index == n)                      //index > n-1, try to get the n-1 num, means it is ok , printf it
        {
            
static int l = 1;
            printf(
"%3d: ", l++);
            
for(int k = 0; k<n; k++) printf("%d "out[k]);
            printf(
" ");
            
return;
        }
        
else if(a[i] != ILLEAGALNUM)
        {
            
out[index] = a[i];
            a[i] 
= ILLEAGALNUM;
            Permutation2(a, index
+1, n);
            a[i] 
= out[index];
        }
    }
}

//修改数据数组表示其使用状态,调用深度表示取第几个数
void Permutation3(int a[], int n)
{
    
static int out[N];
    
static int depth = -1;                      //recursive call depth.
    depth++;
    
for(int i = 0; i < n; ++i)
    {
        
if(depth == n)                      //index > n-1, try to get the n-1 num, means it is ok , printf it
        {
            
static int l = 1;
            printf(
"%3d: ", l++);
            
for(int k = 0; k<n; k++) printf("%d "out[k]);
            printf(
" ");
            depth
--;
            
return;
        }
        
else if(a[i] != ILLEAGALNUM)
        {
            
out[depth] = a[i];
            a[i] 
= ILLEAGALNUM;
            Permutation3(a, n);
            a[i] 
= out[depth];
        }
    }
    depth
--;
}


//额外的数组表示其使用状态,参数表示取第几个数
void Permutation4(int a[], int index, int n)
{
    
static int out[N]; // result array
    static bool m[N] = {1,1,1,1,1,1,1,1,1,1}; // mark array, indicate whether the coorespond element 
                                              
//in array a is already used.
    for(int i = 0; i < n; ++i)
    {
        
if(index == n)                      // if we already get the last num, print it
        {
            
static int l = 1;
            printf(
"%3d: ", l++);
            
for(int k = 0; k<n; k++) printf("%d "out[k]);
            printf(
" ");
            
return;
        }
        
else if(true == m[i])                      // if element i not used
        {
            
out[index] = a[i];
            m[i] 
= false;                      // mark element i as used
            Permutation4(a, index+1, n);                      // recursive to get next num
            m[i] = true;                      // backdate , so that we can try another case
        }
    }
}

 

虽然对于这样的问题效率与空间相差不会特别明显,但是我们还是来比较一下来找出最佳的一个。对于数组使用状态的保存,显然,用第一个方案需要动用一个额外的数组,而并没有提高效率,所以我们应该采用第二个方案:修改数组值的方法。对于当前取的是哪个数,如果我们用传参数的方式,因为在排列过程中,这个递归函数被调用的次数是非常多的。(6个数的全排列就要调用1957次),这样多一个参数, 其每次调用压栈出栈的消耗就显得比较大了, 所以我们推荐用调用深度来表示。


经过上面的讨论, Permutation3就是我们的最佳选择。



posted on 2007-08-26 20:45 SmartPtr 阅读(664) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理