c语言字典序全排列高效算法（非递归）

Question

#include
void swap(int a[100],int j,int k)
{
int temp;
temp=a[j];
a[j]=a[k];
a[k]=temp;
}
void reverse(int a[100],int j,int n)
{ int i,y;
for(i=j+1,y=0;i {swap(a,i,n-y);}
}
void print(int a[100],int n)
{
int i;
for(i=1;i {
printf("%d ",a[i]);
}
printf("\n");
}
int fac(int n)
{
int anw;
if(n==1||n==0)
anw=1;
else
anw=n*fac(n-1);
return anw;
}
void fin(int a[100],int n)
{
int i,j,k;
for(i=n-1;i>=1;i--)
{
if(a[i]<a[i+1])
{j=i;break;}
}
for(i=0;i<n;i++)
{
if(a[j]<a[n-i])
{k=n-i;break;}
}
swap(a,j,k);
reverse(a,j,n);
print(a,n);
}
int main()
{
int i,n,m,y;
int a[100];
scanf("%d",&n);
for(i=1;i<=n;i++)
a[i]=i;
print(a,n);
for(m=1;m<=fac(n)-1;m++)
{fin(a,n);}

return 0;

}

这个代码会超时，想知道怎么才能优化？
这个代码有写错的地方吗？还是只是因为算法太低效才会超时？

Answer 1

#include<stdio.h>
using namespace std;
const int N =105;
int n,m;
int a[N];
void out(){
    for(int i=1;i<=n;i++) printf("%d",a[i]);
    puts("");
}
void swap(int& a,int& b){
    int tmp = a;a=b;b=tmp;
}
void rev(int left,int right){
    while(left<=right){
        swap(a[left],a[right]);
        left++,right--;
    }
}
bool change(){
    int j=n-1;
    for(;j>=1;j--){
        if(a[j]<a[j+1]) break;
    }
    if(j<1) return false;
    int k=n;
    while(a[k]<a[j]) k--;
    swap(a[k],a[j]);
    rev(j+1,n);
    return true;
}
int main()
{
    while(scanf("%d",&n)==1){
        for(int i=1;i<=n;i++) a[i]=i;
        out();
        while(change()) out();
    }
    return 0;
}