c语言 给出一个数怎样输出该数的全排列

c语言 给出一个数怎样输出该数的全排列

递归法：
设输入的数为n，N={1，2，...n}
不断选择数字i,把i从N中剔除，直到N为空集即可
代码如下：
#include
#include
#include

int N;
bool *mark;
int *output, pos = 0;

void AddNumber(int i)
{
bool finish = true;
mark[i] = true;
output[pos++] = i;

int j;
for (j = 0; j < N; j++)
{
if (!mark[j])
{
finish = false;
AddNumber(j);
}
}

if (finish)
{
for (j = 0; j < pos; j++)
printf("%d", output[j] + 1);
printf("\n");
}

pos--;
mark[i] = false;
}

int main()
{
scanf("%d", &N);
mark = (bool *)malloc(sizeof(bool) * N);
output = (int *)malloc(sizeof(int) * N);

memset(mark, (bool)0, sizeof(bool) * N);

int i;
for (i = 0; i < N; i++)
AddNumber(i);

free(mark);
free(output);
system("pause");
return 0;
}

#include<stdio.h>
const int MAXN=100000;
void print_permutation(int n,int *A,int cur)
{
int i,j;
if(cur==n)
{
for(i=0;i<n;i++)
printf("%d",A[i]);
printf("\n");
}
else for(i=1;i<=n;i++)
{
int ok=1;
for(j=0;j<cur;j++)
if(A[j]==i)
ok=0;
if(ok)
{
A[cur]=i;
print_permutation(n,A,cur+1);
}
}
}
int main()
{
int n,cur;
int A[MAXN];
cur=0;
scanf("%d",&n);
print_permutation(n,A,cur);
return 0;
}

参考资料：刘汝佳 (《算法竞赛入门经典》)

C语言版：#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int a[10], book[10], n, k[10], l;
void dfs(int step)
{
int i = 0;
if(step == l + 1)
{
if(a[1] != 0)
{
for(i = 1; i <= l; i++)
{
printf("%d", a[i]);
}
printf(" ");
}
return ;
}
for(i = 0; i < l; i++)
{
if(book[k[i]] == 0)
{
a[step] = k[i];
book[k[i]] = 1;
dfs(step + 1);
book[k[i]] = 0;
}
}
}
int main(void)
{
memset(k, 0, sizeof(k));
memset(book, 0, sizeof(book));
int n;
scanf("%d", &n);
char buf[15] = "";
sprintf(buf, "%d", n);
l = strlen(buf);
    int i = 0;
for(i = 0; i < l; i++)
k[i] = buf[i] - '0';
dfs(1);
    system("pause");//如果通不过编译就试着删除这句话
return 0;
}
C++版：
#include<cstdio>
#include<cstdlib>
#include<cstring>
int a[10], book[10], n, k[10], l;
void dfs(int step)
{
if(step == l + 1)
{
if(a[1] != 0)
{
for(int i = 1; i <= l; i++)
{
printf("%d", a[i]);
}
printf(" ");
}
return ;
}
for(int i = 0; i < l; i++)
{
if(book[k[i]] == 0)
{
a[step] = k[i];
book[k[i]] = 1;
dfs(step + 1);
book[k[i]] = 0;
}
}
}
int main(void)
{
memset(k, 0, sizeof(k));
memset(book, 0, sizeof(book));
int n;
scanf("%d", &n);
char buf[15] = "";
sprintf(buf, "%d", n);
l = strlen(buf);
for(int i = 0; buf[i] != ''; i++)
k[i] = buf[i] - '0';
dfs(1);
return 0;
}