递归思想：
image.png
该算法的奇妙之处在于它的回退能保证经过P处理之后的str能跟输入的保持不变。
1. 全排列：
perm(set, s, e)
{
顺序从set[s]~set[e]中选出一个元素与s交换(即选出一个元素)
调用perm(set, s + 1, e)
直到s>e，即剩余集合已经为空了，输出set
}
image.png
我的最初版本(提供个思路)：
#include
#include
void exchange(char input[],int destination,int point){
char temp;
temp=input[point];
input[point]=input[destination];
input[destination]=temp;
}
void p(char input[],char output[],int start,int end){
int i;
char remember[4];
// 这个不太好动态生成，而且每次执行都要创建一个数组比较浪费空间。
strcpy(remember,input);
// 因为后续的p函数中会修改掉input数组，导致for循环中的数据不再是我们需要的顺序遍历。如果是广度优先遍历(递归是深度优先遍历)则可以减少这一步。
if(start==end-1){
output[start]=input[end-1];
printf("%sn",output);
return;
}
for(i=start;i
output[start]=remember[i];
strcpy(input,remember);
exchange(input,start,i);
p(input,output,start+1,end);
}
}
int main()
{
// 处理字符数组要注意最后的' '也占一位，strlen不计最后的' '
char str[]="abc";
char output[]="abc";
p(str,output,0,strlen(str));
}
代码:
exchange方法:(新方法快那么一点)
通过exchange方法实现记忆式回退。
#include
#include
#define N 24 // 最大排列(len)^23
void exchange(char input[],int destination,int point){
char temp;
temp=input[point];
input[point]=input[destination];
input[destination]=temp;
}
void p(char input[],int start,int end){
// 只要input就可以了，output其实不需要
int i;
if(start==end){
printf("n%s",input);
return;
}
for(i=start;i
exchange(input,start,i);
p(input,start+1,end);
exchange(input,start,i);
}
}
int main()
{
char str[N];
scanf("%s",&str);
p(str,0,strlen(str));
}
image.png
strcpy方法:(老方法)
通过简单粗暴的覆盖方法恢复数组。
#include
#include
void exchange(char input[],int destination,int point){
char temp;
temp=input[point];
input[point]=input[destination];
input[destination]=temp;
}
void p(char input[],char output[],int start,int end){
int i;
char remember[8];
strcpy(remember,input);
if(start==end-1){
output[start]=input[end-1];
printf("%sn",output);
return;
}
for(i=start;i
output[start]=remember[i];
strcpy(input,remember);
exchange(input,start,i);
p(input,output,start+1,end);
}
}
int main()
{
char str[]="abcdefg";
char output[]="abcdefg";
p(str,output,0,strlen(str));
}
image.png
2. 组合：
思路：
把P排列的长度改为用户输入的长度即可，然后再将output全排列。
#include
#include
#define N 24 // 最高可以容纳 23! 种组合
char print[N]="a";
void exchange(char input[],int destination,int point){
char temp;
temp=input[point];
input[point]=input[destination];
input[destination]=temp;
}
void p(char input[],char output[],int start,int end){
int i;
if(start==end-1){
output[start]=input[end-1];
printf("n%s",output);
return;
}
for(i=start;i
output[start]=input[i];
exchange(input,start,i);
p(input,output,start+1,end);
exchange(input,start,i);
}
}
void C(char input[],char output[],int start,int end){
int i;
if(start==end){
output[end]=' ';
printf("n>>>> %s:",output);
p(output,print,0,strlen(output));
}
for(i=start;i
output[start]=input[i];
exchange(input,start,i);
C(input,output,start+1,end);
exchange(input,start,i);
}
}
int main()
{
char str[N];
char output[N];
scanf("%s",&str);
strcpy(output,str);
int c_top=0; // C(c_top,c_bottom);
scanf("%d",&c_top);
C(str,output,0,c_top);
}