算法学习之字符串全排列

#include <stdio.h>
#include <stdlib.h>
#define MAX  50
void swap(char *a,char *b)
{
    char tmp = *a;
    *a = *b;
    *b = tmp;
}
void permutations(char *str,int pos,int n) //pos表示当前位置，n表示字符串的大小
{
    int i;
    if(pos == n)  //如果到最后，说明一次排列完毕，输出排列结果
    {
        for(i = 0; i <= n; i++)
            printf("%c",str[i]);
            printf("\n");
    }
    else
    {
        for(i = pos; i <= n; i++) //让此位置及以后的所有字符和它交换
        {
            swap(&str[pos],&str[i]);
            permutations(str,pos+1,n); //递归进入下一个位置
            swap(&str[pos],&str[i]); //返回的时候再交换回来
        }
    }
}
int main()
{
    char str[MAX];
    scanf("%s",str);
    permutations(str,0,strlen(str)-1);
    return 0;
}

#include <stdio.h>
#include <stdlib.h>
#define MAX  50
void reverse(char *str,int i)
{
    int n = strlen(str) - 1;
    while(i < n)
    {
        char tmp = str[i];
        str[i++] = str[n];
        str[n--] = tmp;
    }
}
int permutations(char *str,int n)
{
    int i,j;
    for(i = n-1; i >= 0 && str[i] >= str[i+1]; i--) //找到ai < ai+1的位置
    {

    }
    if(i == -1)
        return 0;
    for(j = n; j >=0 && str[j] <= str[i]; j--) //找到最右边大于ai的数
    {

    }
    char tmp = str[i];//交换i,j
    str[i] = str[j];
    str[j] = tmp;
    reverse(str,i+1);//逆至i后面的数
    return 1;
}
int main()
{
    char str[MAX];
    scanf("%s",str);
    int n = strlen(str) - 1;
    while(permutations(str,n))
        printf("%s\n",str);
    return 0;
}