发信人: Lerry (想不开·撞树), 信区: Algorithm
标 题: [合集]全排列
发信站: 哈工大紫丁香 (2002年08月13日10:03:18 星期二), 站内信件
────────────────────────────────────────
feelcycle (无是) 于 发信站: 北大未名站 (2002年08月12日12:07:12 星期一), 转信
用回溯法，首先，N个数也不需要一定是1~N,
(ps.全排列有什么用呢？11位就耗4s，每加1位就长1个数量级还多)
只要可以排序出来，是单调的就可以，
首先做一次排序，递增递减都可以，
然后就转换成了对1～N的排序，排序出来将对应的值换为Data[i]就可以了，
也就是说，最后都转换为了1~N自然数的排序。
设置结果存放的数组，R[N],
设标志位进到第几位，设为i,不说那么多了，看代码
void Series(int N){
int i,j;
int *iR=new int[N];
short *bUsed=new short[N];//第i个数是否已经使用
for(j=0;j<N;j++) bUsed[j]=0;
i=0;//初始化
iR[0]=0;
bUsed[0]=1;
while(1){
i++;//进位，下一位重新搜索开始
j=0;
while(j<N){
if(!bUsed[j]){//找到了
bUsed[j]=1;
iR[i]=j;
break;
}
j++;
}
if(j==N)
i=i;//没有找到退回
else if(i==N-1){//如果找到了，输出
for(j=0;j<N-1;j++){
cout<<iR[j]<<",";
}
cout<<iR[N-1]<<endl;
bUsed[iR[i]]=0;//准备回退
}
else continue;
//注意是否要回溯了
back: if(i==0) break;//退无可退，表示已经搜索完全，退出
i--;//没有找到当前项，回退一项
bUsed[iR[i]]=0;//取消回退项的使用标志
j=iR[i]+1;//从下一个位置找起
while(j<N){
if(!bUsed[j]){//找到了
bUsed[j]=1;
iR[i]=j;
break;
}
j++;
}
if(j==N) goto back;//如果没有找到，那么继续回退，
//这里使用goto没有破坏结构化，因为完全可以用加while嵌套完成
}
delete iR;
delete bUsed;
}
────────────────────────────────────────
DailyByte (DailyByte) 于 发信站: 北大未名站 (2002年08月13日00:37:48 星期二), 转信
构造生成，速度快，效率高
#include <iostream.h>
#include <stdlib.h>
const int max = 1001;
int n,list[max];
int main()
{
int i,maxi;
for(;;) {
cin >> n;
if (n<=0 || n>max) break;
for (i=1;i<=n;i++)
list[i] = -i;
for (;;) {
cout << "# ";
for (i=1;i<n;i++)
cout << abs(list[i]) << ' ';
cout << abs(list[n]) << endl;
maxi = 0; list[0] = 0;
for (i=1;i<=n;i++)
if (abs(list[i]) > abs(list[maxi])) {
if ((list[i]<0 && i>1 && abs(list[i-1])<abs(list[i]))||
(list[i]>0 && i<n && abs(list[i+1])<abs(list[i])) )
maxi = i;
}
if (maxi==0) break;
if (list[maxi]>0) {
list[0] = list[maxi];
list[maxi] = list[maxi+1];
list[maxi+1] = list[0];
maxi++;
} else {
list[0] = list[maxi];
list[maxi] = list[maxi-1];
list[maxi-1] = list[0];
maxi--;
}
for (i=1;i<=n;i++)
if (abs(list[i])>abs(list[maxi]))
list[i] = -list[i];
}
}
return 1;
}
────────────────────────────────────────
feelcycle (无是) 于 发信站: 北大未名站 (2002年08月13日09:51:35 星期二), 转信
怎么说呢，全排列，想多快是不可能的，
所以千万慎用速度快，给你个12就够你难受一阵子，
其次就是回溯法在认为编程水平等条件一致的情形下是
最快的算法，下面是我的算法和你的算法的对比，
我拿掉了你的最外层循环，直接将n作为参数：
在10的情形下，debug版：
我的算法是690ms,你的算法是2564ms.
本来没想比速度的，看见你的速度快，效率高，
而且max居然定义为1001，实在忍不住了，
就算是100，你的机器能算出来吗？？？
ps.上面比较时其实都拿掉了屏幕输出的代码。
────────────────────────────────────────
--
※ 修改:·Lerry 於 08月13日10:04:06 修改本文·[FROM: 天外飞仙]