算法：求全排列的递归算法

[复制链接]

字体大小: 正常放大

知道了

14 主题	9 听众	49 积分

升级 46.32%

TA的每日心情

	擦汗 2015-5-5 09:17

签到天数: 13 天

[LV.3]偶尔看看II

自我介绍: 往往

电梯直达

1^#

发表于 2015-4-16 14:28 |只看该作者 |倒序浏览

|招呼Ta 关注Ta

/*
使用递归方法求全排列
*/

#include<stdio.h>

int sum=0;
int main(){
      int n,i;
      char *p;
      void perm(char *,int,int);

      scanf("%d",&n);
      p=new char[n];
      for(i=0;i<n;i++){
            getchar();
            scanf("%c",p+i);
      }

      perm(p,0,n-1);
      printf("==>%d",sum);

      return 0;
}

void perm(char *p,int s,int e){
      int i;
      void swap(char*,char*);

      if(s==e){
            printf("%s\n",p);
            sum++;
            return ;
      }
      else{
            for(i=s;i<=e;i++){
                     swap(p+s,p+i);
                     perm(p,s+1,e);
                     swap(p+s,p+i);
            }
      }
}

void swap(char *a,char *b){
      int tmp=*a;
      *a=*b;
      *b=tmp;
}

======================================================================
1.关于思路：当仅有一个元素时，全排列就是它自己本身一个；对于多个元素的序列，其全排列为去掉某个元素的全排列，再在这些全排列序列中加入该元素（如果某一个排列序列包含n个元素，那么加入的方案就有n+1个），这等价于每个元素做打头元素，后续的子序列的全排列，而for循环就是体现这一点。
2.关于输出：一开始我怎么也找不到输出的好办法！第一是尝试在下一层递归前输出字符，发现不行；后来在递归回来后再输出一次，还是不行……总之尝试了很多次都没有效果。最后从另一位大神中才想到有直接输出字符串的控制符！坑呐，说明自己对语法不够熟练，加紧练习！

zan