全排列问题

方法一：

#include<stdio.h>
#define max 4
int vis[10],line[10];//vis数组用于标记数据是否访问过，line数组用于记录数据。
int dfs(int pos)//pos用于记录当前处理的位置
{ int i;
   if(pos==max+1)//当pos==max时还要继续处理最后一个数所以为max+1
   {
       for(i=1;i<=max;i++)
       {
           printf("%d",line[i]);
       }
       printf("\n");
   }
    for(i=1;i<=max;i++)
    {
        if(vis[i]==0)//当这个数并没有被标记也就是还没有进入line数组中
        {
            line[pos]=i;//i并在之前并没有进入line中所以把i放进去
            vis[i]=1;//i已经进入了line中，所以标记为1
            dfs(pos+1);//处理下个位置
            vis[i]=0;//回溯
        }
    }
}
int main()
{
    dfs(1);
}

分析：从第一个位置开始处理，再在递归函数里面加个循环如果1~max里面的数还没有被访问过就进入记录数据的数组line并把数据标记为以访问。递归处理下个位置处理完max位置时输出line数组。这相当于人自己做全排列时先固定一个然后剩下的依次交换位置。

方法二：

分析先固定一个值然后让其他值互相换位置。（递归结束时要将位置换回来然后才能继续）。

 1 #include<stdio.h>
 2 #define max 4
 3 int list[max]={1,2,3,4};
 4 void swap(int x,int y)//交换
 5 {
 6     int term;
 7     term=list[x];
 8     list[x]=list[y];
 9     list[y]=term;
10 }
11 void dfs(int start,int end)
12 {
13     int i;
14     if(start>end)//当start大于end时表面已经处理完了最后一个数据
15     {
16         for(i=0;i<max;i++)
17         printf("%d",list[i]);
18         printf("\n");
19     }
20     for(i=start;i<=end;i++)
21     {
22         swap(start,i);
23         dfs(start+1,end);
24         swap(start,i);
25     }
26 }
27 int main()
28 {
29     dfs(0,3);
30 }

全排列问题

推荐阅读