全排列递归思路（c）版本

附上 c 版本

#include<stdio.h>
#include<string.h>
#include<stdlib.h>

#define MAX 10

char * subElement(char *input,int pos);
void permutation(char *input,int len, int pos, char *p);

char *subElement(char *input, int pos)
{
    int i = 0;
    char *ret = (char*)malloc(MAX*sizeof(char));
    char *tmp = ret;
    while( input != NULL && i < MAX )
    {
        if(i != pos)
        {
            *tmp = *input;
            tmp++;
        }
        input++;
        i++;
    }
    tmp[i] = '\0';
    return ret;
}
void permutation(char *input, int len, int pos, char *p)
{
    int i = 0;

    if(len == 0)
    {
        return;
    }
    //only one element
    if(len == 1)
    {
            printf("{%s}\n",input);
            return;
    }

    char *lp = (char *)malloc(sizeof(char)*MAX);
    memset(lp,'\0',sizeof(char)*MAX);

    char *sp = subElement(input, pos);
    int plen = 0;
    if(p != NULL)
    {
        plen = strlen(p);
        strcpy(lp,p);
    }

    lp[plen] = input[pos];
    lp[plen+1] = '\0';

    int slen = strlen(sp);
    if(slen == 1)
    {
        lp[plen+1] = *sp;
        printf("{%s}\n",lp);
        return;
    }

    for(i = 0; i < slen; i++)
    {
        permutation(sp,len-1,i,lp);
    }
    free(sp);
    free(lp);
}
void main()
{
    int i = 0;
    char instr[MAX];
    printf("write elements:");
    scanf("%s",instr);
    char *parent = NULL;
    for(i = 0; i < strlen(instr); i++)
    {
        permutation(instr,strlen(instr), i, parent);
    }
}

 

关于这类问题的一个数学解释，很强大。

http://episte.math.ntu.edu.tw/articles/mm/mm_10_2_04/index.html

留下链接慢慢学习。