c语言求全排列

Question

Description
输入一个整数n(<=6)，按顺序输出1~n的全排列，每个排列占一行。注意数字以空格间隔，行末没有空格。
Sample Input
3
Sample Output
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

Answer 1

用迭代算法简单些, 就是速度慢许.

算法为:
为求1 ~ n个整数的函数 permutation,
* 如果n = 2, 只有两种排列方式, 即 (1, 2) (2, 1)
* 迭代计算1 ~ n-1个整数的全排列
* 将n插入所得到的1 ~ n-1的全排列的任意位置得到1 ~ n的全排列.

Answer 2

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

char string[]="123456789a";
int used[10]={0};
char output[10];
int length;

void Fun(int d)
{
int i;

for(i=0;i<=length;i++)
{
if(!used[i])
{
used[i]=1;
output[d]=string[i];
if(d==length)
{
for(d=0;d<length;d++)
{
if(output[d]=='a')
printf("10 ");
else printf("%c ",output[d]);
}
if(output[length]=='a')
printf("10\n");
else
printf("%c\n",output[length]);
}
else
Fun(d+1);
used[i]=0;
}
}
}

int main()
{
int n;
scanf("%d",&n);

string[n]=0;
length=strlen(string)-1;

Fun(0);

return 0;
}赞同2|评论

Answer 3

#include <stdio.h>
#include <string.h>
void perm(char list[],int k,int m)
{
if(k==m)
{
for(int i=0;i<=m;i++)
printf("%c ",list[i]);
printf("\n");
}
else
for (int i=k;i<=m;i++)
{
int t;
t=list[k];list[k]=list[i];list[i]=t;
perm(list,k+1,m);
t=list[k];list[k]=list[i];list[i]=t;
}
}
void main()
{
char str[1000];
int i,n;
scanf("%d",&n);
for(i=1;i<=n;i++)
str[i-1]=i+'0';
str[i-1]='\0';
perm(str,0,strlen(str)-1);
}