字符全排列(递归)小总结(一个菜鸟的历程)

递归 | 2017-05-25 01:59:11 | 84次阅读 | 1评

前几天在写在线测试的时候,碰到一个全排列的问题,写了好几个代码,就是过不了,纠结了几天,最后只能求救于百度了,发现原来是理解题目有偏差,还是太菜了。。。。
我将我的代码写出来,有需要的可以看看,当然,如果发现我存在的漏洞,也请指出来。
Description
将输入的一个字符串中的所有元素进行排序并输出。

Input
不超过5个字符的字符串

Output
所有字符按出现的先后顺序全排列的结果

Sample Input
abc

Sample Output
abc 
acb 
bac 
bca 
cab 
cba ​
刚开始没怎么想,以为挺简单的,就啪啪啪(别想歪了)的写了一堆代码。
程序1【代码】:

include

include

void paixu(char a[],int k,int n)
{
    int i;
    char t;
    if(k==n-1)
    {
        for(i=0;i<n;i++)      //输出排列
            printf("%c ",a[i]);
        printf("\n");
    }
    else              //产生a[k],...,a[n-1]的各种排列
    {
        for(i=k;i<n;i++)        
        {
            t=a[k];a[k]=a[i];a[i]=t;
            paixu(a,k+1,n);     //产生a[k+1],...,a[n-1]的各种排列
            t=a[k];a[k]=a[i];a[i]=t;
        }
    }
}
int main()
{
    int n;
    char a[10];
    scanf("%s",&a);
    n=strlen(a);
    paixu(a,0,n);
    return 0;
}

【运行结果】:
abc
a b c
a c b
b a c
b c a
c b a
c a b
运行之后,一比对,发现没有按照所输入的字母的顺序进行全排列,那就改代码呗。

要按输入字母的顺序输出,行,我就让你这么输出
程序2【代码】:

include

include

void print(char a[],int n, int cur,char b[])
{
int i,j;
if(cur==n) 
{
for(i=0;i<n;i++)                             //输出排列
printf("%c",a[i]);
printf("\n");
}
else
{
for(j=0;j<n;j++)
{
int ok=1;
for(i=0;i<cur;i++)
{
if(a[i]==b[j])                  //判断字符是否出现,未出现则跳出循环
{
ok=0;
}
}
if(ok)                       //按输入顺序将字符赋给a数组
{
a[cur]=b[j];                              
print(a,n,cur+1,b);
}
}
}
}
int main()
{
int n;
char a[100],b[100];
scanf("%s",&b);          //用b数组保存输入的字符串
n=strlen(b);
print(a,n,0,b);         //用a数组保存将输出的字符串
return 0;
}

【运行结果】:
abc
abc
acb
bac
bca
cab
cba
比较一下,现在应该对了吧,结果依旧wrong answer,然后检查后发现碰到重复的字符,则无结果输出,,还是太菜。。。思考不全面。

然后改程序改了半天,一头雾水,只有全部推翻,重写。
程序3【代码】:

include

include

int repetition(char *str, int begin, int k){   //判断从子串的第一个字符串开始,直到k-1位置,看是否有重复的字符
    int i, flag;
    for (i = begin, flag = 1; i < k; i ++) {
        if (str[i] == str[k]) {
            flag = 0;
            break;
        }
    }
    return flag;
}

void print(char* str,int begin,int end)
{
char t;
    if (begin == end)
    {
        printf("%s\n",str);
        return;
    }
else
{
        int i;
        for (i = begin; i < end; i++)
        {
            if (repetition(str,begin,i))      //为避免生成重复排列,当不同位置的字符相同时不再交换
            {
t=str[begin];str[begin]=str[i];str[i]=t;
                print(str,begin+1,end);
t=str[begin];str[begin]=str[i];str[i]=t;
            }
        }
    }
}
int main()
{
int n;
char b[100];
scanf("%s",&b);
n=strlen(b);
print(b,0,n);  
return 0;
}
【运行结果】:
abbb
abbb
babb
bbab
bbba
【运行结果】:
abc
abc
acb
bac
bca
cba
cab

​重复的字符也可以输出来了,但是又回到了最初的问题,没有按照输入字母的顺序输出。

好吧,我无语了,接着我用了一个最笨的方法,我把上面写的两个程序拼成了一个程序,程序2能按输入顺序输出,程序3能输出重复的数(消除相同的数),两个一结合不就行了。
程序4【代码】:

include

include

void swap(char* str,int a,int b)
{
    char tmp = str[a];
    str[a] = str[b];
    str[b] = tmp;
}

int repetition(char *str, int begin, int k){   //判断从子串的第一个字符串开始,直到k-1位置,看是否有重复的字符
    int i, flag;

    for (i = begin, flag = 1; i < k; i ++) {
        if (str[i] == str[k]) {
            flag = 0;
            break;
        }
    }

    return flag;
}

void print2(char* str,int begin,int end)
{
char t;
    if (begin == end)
    {
        printf("%s\n",str);
        return;
    }else{
        int i;
        for (i = begin; i <= end; i++)
        {
            if (repetition(str,begin,i))
            {
t=str[begin];str[begin]=str[i];str[i]=t;
                print2(str,begin+1,end);
t=str[begin];str[begin]=str[i];str[i]=t;
            }
        }
    }
}
void print1(char a[],int n, int cur,char b[])
{
int i,j;
if(cur==n)
{
for(i=0;i<n;i++)
printf("%c",a[i]);
printf("\n");
}
else
{
for(j=0;j<n;j++)
{
int ok=1;
for(i=0;i<cur;i++)
{
if(a[i]==b[j])
{
ok=0;
}
}
if(ok)
{
a[cur]=b[j]; 
print1(a,n,cur+1,b);
}
}
}
}
int main()
{
int n,i,j,m;
char a[100],b[100];
scanf("%s",&b);
n=strlen(b);
m=0;
for(i=0;i<n;i++)
{
for(j=i+1;j<n;j++)
{
if(b[j]==b[i])
{
m=1;
break;
}
}
}
if(m==0)
print1(a,n,0,b);          //不含重复字符
else
print2(b,0,n-1);   //含重复字符
return 0;
}

【运行结果】:
abc
abc
acb
bac
bca
cab
cba

【运行结果】:
abb
abb
bab
bba

现在对了吧!but依旧wrong answer, 我的心中仿佛有一万匹草泥马奔腾而过。
最终,求救百度了。
程序5【代码】:
​#include

include

using namespace std;

void permute1(string prefix,string str)
{
if(str.length()==0)
cout<>a;
permute1(a);
return 0;
}
​【运行结果】:
abc
abc
acb
bac
bca
cab
cba
【运行结果】:
abb
abb
abb
bab
bba
bab
bba

对比一下,发现原来碰到一样的排列不能删除,我果然是菜鸟,太自以为是了,没理解题目的意思就动手写代码​,果然是一个不明智的决定。
小伙伴们,做任何事之前一定要想清楚啊!
谋定而后动,知止而有得!,希望对你们有所帮助。



博友评论,共1条
Avatar
1楼:mastertodd 发表于 2017-06-17 12:25  
赞一个
最新评论