前几天在写在线测试的时候，碰到一个全排列的问题，写了好几个代码，就是过不了
，纠结了几天，最后只能求救于百度了
，发现原来是理解题目有偏差
，还是太菜了。。。。
我将我的代码写出来，有需要的可以看看
，当然，如果发现我存在的漏洞，也请指出来。
Description
将输入的一个字符串中的所有元素进行排序并输出。
Input
不超过5个字符的字符串
Output
所有字符按出现的先后顺序全排列的结果
Sample Input
abc
Sample Output
abc
acb
bac
bca
cab
cba
刚开始没怎么想，以为挺简单的，就啪啪啪（别想歪了
）的写了一堆代码。
程序1【代码】：
#include <stdio.h>
#include<string.h>
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<stdio.h>
#include <string.h>
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 <stdio.h>
#include<string.h>
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 <stdio.h>
#include<string.h>
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<iostream>
#include<string>
using namespace std;
void permute1(string prefix,string str)
{
if(str.length()==0)
cout<<prefix<<endl;
else
{
for(int i=0;i<str.length();i++)
permute1(prefix+str[i],str.substr(0,i)+str.substr(i+1,str.length()));
}
}
void permute1(string s)
{
permute1("",s);
}
int main()
{
int i=0;
char a[100];
cin>>a;
permute1(a);
return 0;
}
【运行结果】：
abc
abc
acb
bac
bca
cab
cba
【运行结果】：
abb
abb
abb
bab
bba
bab
bba
对比一下，发现原来碰到一样的排列不能删除，我果然是菜鸟，太自以为是了，没理解题目的意思就动手写代码
，果然是一个不明智的决定。
小伙伴们，做任何事之前一定要想清楚啊！
谋定而后动，知止而有得！
，希望对你们有所帮助。