排列组合(C递归版)

鸣谢:
https://blog.csdn.net/lanmo555/article/details/22409883
http://www.jb51.net/article/93488.htm

递归思想：

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<stdio.h>
#include<string.h>
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("%s\n",output);
        return;
    }
    for(i=start;i<end;i++){
        output[start]=remember[i];
        strcpy(input,remember);
        exchange(input,start,i);
        p(input,output,start+1,end);
    }
}

int main()
{
    // 处理字符数组要注意最后的'\0'也占一位，strlen不计最后的'\0'
    char str[]="abc";
    char output[]="abc";
    p(str,output,0,strlen(str));
}

代码:

exchange方法:（新方法快那么一点）

通过exchange方法实现记忆式回退。

#include<stdio.h>
#include<string.h>
#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<end;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<stdio.h>
#include<string.h>
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("%s\n",output);
        return;
    }
    for(i=start;i<end;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<stdio.h>
#include<string.h>

#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<end;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]='\0';
        printf("\n>>>> %s:",output);
        p(output,print,0,strlen(output));
    }
    for(i=start;i<strlen(input);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);
}