全排列（递归）

  在学习算法分析的时候，一开始会接触到递归算法，递归算法案例往往很容易理解。但是如何根据实际情况去设计递归算法往往是难题。接下来通过全排列案例来讲述一下递归的用法。

1.全排列

    给定一串无重复的字符或数字，输出其有所有排列，并统计其共有排列个数。

    例：给定个数n（n<10），=输入n个数字或字符，输出其所有排列及其排列个数

例 ：    输入：3

                     123

     输出：123  132  213  231  321  312

                       6

    算法思想：递归

    数学归纳法分析：

N =1；排列个数 1  

 N =2；排列个数 3  = 2 * 1

 N =3；排列个数 6  = 3 * 2 * 1

 N=4；排列个数24   = 4 * 3 * 2 * 1 

 …..

N = n;排列个数n * （n-1）* (n-2) *(n-3) ….* 1

以1234为例：

由图可以发现：

首位有四种数字交换，第二位有三种交换，第三位有两种，最后一位无交换（也可以是一种交换）。

 这样我们就从理解了全排列的排列方式，从而就更方便的写代码了。

以123为例：从最高位开始循环，

第三层有3个循环

第二层有2个循环

 第一层有1个循环

如果有4层循环，就是依次第四层有4个循环，依次向下嵌套。

如果有n层循环，就是依次第n层有n个循环，依次向下嵌套。

就像金字塔一样，依次向上叠加。

以123全排列为例就是：

最高位可以有3个数交换

 代码实现：递归

void perm(char list[],int k,int m)
{
	if(k==m) //当循环到最后一层时（末尾），输出排列 
	{
		count++;
		printf("%s\n",list);
	}
	for(int i=k;i<=m;i++)   
	{	
			swap(&list[k],&list[i]);  //交换位置 
			perm(list,k+1,m);        //递归调用 
			swap(&list[k],&list[i]);
	}
}

上述代码就是关键递归函数，但是很不容易看懂。

下图图解更方便理解这个递归调用的核心。

 以字符串list =“123”为例子：

 当循环到最后一层时输出循环。

正好符合排序个数 N=3 时

排序个数等于  3 *  2 *  1 。

2. 完整代码如下：

#include <stdio.h>
#include <string.h>
int count=0;
void swap(char *a,char *b) 
{
	char temp;
	temp=*a;
	*a=*b;
	*b=temp;
}
int finish(char list[],int k,int i)   
{
	if(i>k)
	{
		for(int j=k;j<i;j++)
			if(list[j]==list[i])
				return 0;
	}
	return 1;
}
void perm(char list[],int k,int m)
{
	if(k==m) //当循环到最后一层时（末尾），输出排列 
	{
		count++;
		printf("%s\n",list);
	}
	for(int i=k;i<=m;i++)   
	{	
			swap(&list[k],&list[i]);  //交换位置 
			perm(list,k+1,m);        //递归调用 
			swap(&list[k],&list[i]);
	}
}
int main()
{
    char a[10];
    scanf("%s",a); 
    int n =strlen(a);
    printf("排序序列为：\n"); 
	perm(a,0,n-1); 
	printf("总排序个数为\n"); 
	printf("%d",count); 
	return 0;
}

 3.总结：递归

递归简单来说：就是在运行过程中不断调用自己，直到碰到终止条件，返回结果的过程。

核心就是三点：

1.大问题拆分成小问题

2.原问题和子问题求解思路相同，数据规模不同

3.存在递归终止条件

实际做题中也存在第四点：

当不满足终止条件时，要如何缩小函数值并让其进入下一层循环中

递归的根本思想就是数学归纳法分析。

上述递归条件：

1.循环递归，无返回值，递归到最深处k =m 处停止递归。