首页 > 学院 > 开发设计 > 正文

所有情况下全排列的实现

2019-11-14 10:15:07
字体:
来源:转载
供稿:网友

全排列是将一组数按一定顺序进行排列,如果这组数有n个,那么全排列数为n!个。我们在此需要考虑重复情况。应用递归算法实现排序。

1.如下程序,可实现全排列,但是缺少判断函数不能处理重复情况。

#include <stdio.h>int permutation( char s[], int b, int e ){	if( 0 <=b && b <= e)	{		if( b == e )		{			PRintf( "%s/n",s);			}		else		{			int i;			for( i=b; i<=e; i++)			{				char c = s[b];				s[b] = s[i];				s[i] = c;				permutation( s, b+1, e);				c = s[b];				s[b] = s[i];				s[i] = c;				}			}		}}int main() {	char s[] = "123";	permutation( s,0,2);		return 0;}2.加入判断函数后可处理重复情况。

#include <stdio.h>int is_swap(char s[], int begin, int k){	int i;	for (i = begin; i < k; i ++)		if(*(s + i) == *(s + k))			return 0;	return 1;}void permutation(char s[], int b, int e){    if( (0 <= b) && (b <= e) )    {        if( b == e )        {            printf("%s/n", s);        }        else        {            int i = 0,m = 0,zx = 1;                        for(i=b; i<=e; i++)            	if(is_swap(s,b,i))            	{                	char c = s[b];                	s[b] = s[i];                	s[i] = c;                                                	permutation(s, b+1, e);                                	c = s[b];                	s[b] = s[i];                	s[i] = c;            	}        }    }}int main(){    char s[] = "aabb";        permutation(s, 0, sizeof(s) - 2);    printf("%d",sizeof(s));        return 0;}3.优化,写出交换函数,直接调用调换函数进行调换。

#include <stdio.h>//#include <stdlib.h>#include <string.h>void swap(char *str, int begin, int k){	char tmp;	tmp = *(str + begin);	*(str + begin) = *(str + k);	*(str + k) = tmp;}int is_swap(char *str, int begin, int k){	int i;	for (i = begin; i < k; i ++)		if(*(str + i) == *(str + k))			return 0;	return 1;}void permutation(char *str, int begin, int end){	int k;	if (begin == (end - 1)) 	{		printf("%s/n", str);		return;	}	for (k = begin; k < end; k++)		if(is_swap(str, begin, k)) 		{			swap(str, begin, k);			permutation(str, begin + 1, end);			swap(str, begin, k);		}}int main(void){	char str[10];	int length;	gets(str);	length = strlen(str);	printf("%d/n", length);	permutation(str, 0, length);	return 0;}


发表评论 共有条评论
用户名: 密码:
验证码: 匿名发表