全排列的递归算法(C语言)

r囧r小猫 2022-03-07 11:41 349阅读 0赞

**全排列的递归实现**  
      为方便起见，用123来示例下。123的全排列有123、132、213、231、312、321这六种。首先考虑213和321这二个数是如何得出的。显然这二个都是123中的1与后面两数交换得到的。然后可以将123的第二个数和每三个数交换得到132。同理可以根据213和321来得231和312。因此可以知道——**全排列就是从第一个数字起每个数分别与它后面的数字交换。**  
**根据规律，可以列出递归伪代码:**  
**allArrange(str,k,m)  
\{  
if k==m print;  
for i=k to m \{  
swap(str,k,i); //k为第k个数  
allArrange(str,k+1,m);  
swap(str,k,i);\} //注意，因为递归有回溯的过程，所以需要把数字重新调换回来变为”初始“的排列。**  
\}

**程序代码如下：**

#include<stdio.h>
    #include<string.h>
    void swap(char *a,char *b)
    {
    	char temp;
    	temp = *a;
    	*a = *b;
    	*b = temp;	
    }
    
    void  Allarrange(char *str,int k,int len)
    {
    	int i;
    	if(k==len)
    	{
    		static int s_i=1;
    		printf("第%d种排列为:\t%s\n",s_i++,str);
    	}
    	else
    	{
    		for(i=k;i<=len;i++)
    		{
    			swap(str+i,str+k);
    			Allarrange(str,k+1,len);
    			swap(str+i,str+k);
    		}
    	}
    }
    
    int main()
    {
    	char str[10];
    	printf("请输入排列的字符串："); 
    	gets(str);
    	Allarrange(str,0,strlen(str)-1);
    	return 0;
    }

**运行效果截图：**  
![在这里插入图片描述][20190316211255567.png]  
**递归的过程不易理解，可以画递归树帮助理解。以"123"为例:**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNTUyNTMz_size_16_color_FFFFFF_t_70]  
**注意以上的方法没有考虑到重复数字，如112将会输出：**  
![在这里插入图片描述][20190316212321430.png]  
**而去重的全排列就是从第一个数字起每个数分别与它后面非重复出现的数字交换。用编程的话描述就是第i个数与第j个数交换时，要求\[i,j)中没有与第j个数相等的数。**

**下面给出完整代码：**

#include<stdio.h>
    #include<string.h>
    int IsSame(char *str,int s_First,int s_End)
    {
    	int i;
    	for(i = s_First ; i < s_End ; i++)
    	{
    		if(str[i]==str[s_End])
    		return 0;
    	}
    	return 1;
    }
    
    void swap(char *a,char *b)
    {
    	char temp;
    	temp = *a;
    	*a = *b;
    	*b = temp;	
    }
    
    
    void  Allarrange(char *str,int k,int len)
    {
    	int i;
    	if(k==len)
    	{
    		static int s_i=1;
    		printf("第%d种排列为:\t%s\n",s_i++,str);
    	}
    	else
    	{
    		for(i=k;i<=len;i++)
    		{
    			if(IsSame(str,k,i))
    			{
    				swap(str+i,str+k);
    				Allarrange(str,k+1,len);
    				swap(str+i,str+k);
    			}
    		}
    	}
    }
    
    int main()
    {
    	char str[10];
    	printf("请输入排列的字符串："); 
    	gets(str);
    	Allarrange(str,0,strlen(str)-1);
    	return 0;
    }

**运行效果截图：**  
![在这里插入图片描述][20190316214202385.png]

[20190316211255567.png]: /images/20220307/30e47c07eaac4523b1740b8c879f941b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNTUyNTMz_size_16_color_FFFFFF_t_70]: /images/20220307/cae508b4919c4627ba3960920d5c7c46.png
[20190316212321430.png]: /images/20220307/c25a3513a63a4639808e41ab99460a4c.png
[20190316214202385.png]: /images/20220307/1dc8ec826c174ea1899f065224ef5cc1.png