全排列

现在给定n（n>=1）个元素组成的集合，输出该集合所有可能的排列，例如：集合{a,b,c}的所有可能排列{(a,b,c),(a,c,b),(b,a,c),(b,c,a),(c,a,b),(c,b,a)}求给定字符串的所有排列。

和上文相同，首先我们要考虑使用递归的两个条件：

第一：这个问题是否可以分解为形式相同但规模更小的问题？

第二：如果存在这样一种分解，那么这种分解是否存在一种简单情境？

第一点，是否存在一种符合条件的分解。分析发现，若有集合{a,b,c,d},全排列问题可由下列排列组成：

1）以a开头后面跟着（b,c,d）的所有排列；

2）以b开头后面跟着（a,c,d）的所有排列；

3）以c开头后面跟着（a,b,d）的所有排列；

4）以d开头后面跟着（a,b,c）的所有排列；

所以将问题分解为小问题的线索就是“后面跟着。。。。的所有排列”，也就是说，如果能够解决n-1个元素集合的排列问题，就可以解决n个元素集合的排列问题。

第二点，一种简单的情景。最简单的情景就是将所有字符顺序输出。

代码如下：（以下代码是对数字进行全排列，若要对字符进行全排列，改动类型就好）

#include<cstdio>

void swap(int* a,int* b){

int temp=*a;

*a=*b;

*b=temp;}

void perm(int *a,int i,int n){

    int j;

    if(i==n){

        for(j=0;j<=n;j++)

        printf("%d",a[j]);

        printf(" ");}

    else{

        for(j=i;j<=n;j++){

        swap(&a[i],&a[j]);

        perm(a,i+1,n);

        swap(&a[i],&a[j]);}

}

    }

int main(){

int a[]={1,2,3,4};

perm(a,0,3);

return 0;}