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

#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;

}

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

8个回答

#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;
}


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");
}

代码有缺失。。请补充完整。。你想要实现的是什么功能哪????字符串翻转??

sssssssssakura
你猜我有多动心 这个代码有写错的地方吗?还是只是因为算法太低效才会超时?
接近 4 年之前 回复
sssssssssakura
你猜我有多动心 回复人类新纪元开始了: 对呀 我就是这样来翻转的,而且n最大只会是8,不大可能因为这个超时吧
接近 4 年之前 回复
shen_wei
shen_wei 数组翻转,根据数组下标来实现快。。
接近 4 年之前 回复
sssssssssakura
你猜我有多动心 void print(int a[],int n) { int i; for(i=1;i<=n;i++) { printf("%d ",a[i]); } printf("\n"); }
接近 4 年之前 回复
sssssssssakura
你猜我有多动心 有缺失吗?我是要实现数组的翻转
接近 4 年之前 回复
sssssssssakura
你猜我有多动心 void reverse(int a[100],int j,int n) { int i,y; for(i=j+1,y=0;i<n;i++,y++) {swap(a,i,n-y);} }
接近 4 年之前 回复

小优化,二分查找[j+1,n]得到k
for(i=0;i<n;i++)
{
if(a[j]<a[n-i])
{k=n-i;break;}
}
改成

int left = j+1,right = n;
while(left<=right){
     int mid = (left+right)/2;
     if(a[mid]>a[j]) {
        k = mid;
            left = mid+1;
     }else{
        right =mid-1;
     }
}

sssssssssakura
你猜我有多动心 还是不行...
接近 4 年之前 回复
 for(m=1;m<=fac(n)-1;m++)

每次循环fac都会运行,复杂度是原先的n倍

改成

int temp = fac(n)-1;
 for(m=1;m<=temp;m++)

另外,这代码风格太糟糕, 比如i,j 变量最好在{} 内定义使用,不然很容易搞乱掉,我写个给你看一下吧

不过福州大学的acm队很强啊,acm-icpc区域赛的时候他们经常拿金奖的说

sssssssssakura
你猜我有多动心 回复zjck1995: 哈哈哈是啊 福州计算机专业能拿得出手的只有ACM了![图片说明](http://forum.csdn.net/PointForum/ui/scripts/csdn/Plugin/001/face/22.gif)是那都是大佬们啊,像我这种大一小白做起题来生不如死
接近 4 年之前 回复

另外还能优化的使利用二分+线段树(区间更新,单点询问) ,这样找到j的复杂度是O((logn)^2), 不过代码量就有点长了

sssssssssakura
你猜我有多动心 啊。。。我是初学者基础很差,我们还没有学到这些,这是考查函数的题目
接近 4 年之前 回复

在哪个oj上的题目?

sssssssssakura
你猜我有多动心 老师课堂的给的练习题,https://vpn.fzu.edu.cn/CSCO+0h756767633A2F2F71662E736D682E7271682E7061++/c/Uploads/Problem/7_5Permutation.pdf
接近 4 年之前 回复
 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])  /// 在这里请把 j 修改成 i 这样就不会出错了。。。因为j没有初始化
{k=n-i;break;}
}
swap(a,j,k);
reverse(a,j,n);
print(a,n);
}
sssssssssakura
你猜我有多动心 有初始化啊,if(a[i]<a[i+1]) {j=i;break;}这里不就是吗
接近 4 年之前 回复
Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问
相关内容推荐