发信人: ycs830()
整理人: girlrong(2000-03-08 18:49:15), 站内信件
|
从1到N，输出全排列，共N！条。试试看！
--
※ 来源:．月光软件站 http://www.moon-soft.com．[FROM: 202.96.78.130]
发信人: girlrong (阿蓉), 信区: CLanguage
标 题: Re: 输出全排列，谁有更好的方法？
发信站: 网易 BBS (Tue Nov 9 10:55:34 1999), 转信
【 在 ycs830 (老山羊) 的大作中提到: 】
: 从1到N，输出全排列，共N！条。试试看！
用N进制的方法吧。设一个N个单元的数组，对第一个单元做加一操作，满N进
一。每加一次一就判断一下各位数组单元有无重复，有则再转回去做加一操作，没
有则说明得到了一个排列方案。
这种方法的要点就在于设计好的判断有无重复单元的算法，设计得好可以加快速度，
设计得不好速度就不敢恭维了。
输出全排列在程序设计中很有用，大家都来提供点好方法吧。
--
※ 来源:．网易 BBS bbs.netease.com．[FROM: 202.103.244.15]
发信人: ycs830 (老山羊), 信区: CLanguage
标 题: Re: 输出全排列，谁有更好的方法？
发信站: 网易虚拟社区 (Tue Nov 9 11:03:29 1999), 站内信件
【 在 girlrong (阿蓉) 的大作中提到: 】
: 【 在 ycs830 (老山羊) 的大作中提到: 】
: : 从1到N，输出全排列，共N！条。试试看！
: 用N进制的方法吧。设一个N个单元的数组，对第一个单元做加一操作，满N进
: 一。每加一次一就判断一下各位数组单元有无重复，有则再转回去做加一操作，没
: .......
不敢恭维！
--
※ 来源:．月光软件站 http://www.moon-soft.com．[FROM: 202.96.78.130]
发信人: supermario (Mario), 信区: CLanguage
标 题: Re: 输出全排列，谁有更好的方法？
发信站: 网易虚拟社区 (Tue Nov 9 11:03:55 1999), 站内信件
【 在 girlrong (阿蓉) 的大作中提到: 】
: 【 在 ycs830 (老山羊) 的大作中提到: 】
: : 从1到N，输出全排列，共N！条。试试看！
: 用N进制的方法吧。设一个N个单元的数组，对第一个单元做加一操作，满N进
: 一。每加一次一就判断一下各位数组单元有无重复，有则再转回去做加一操作，没
: .......
这种算法应该避免判断有无重复，要不然算法时间就会是直线上升，
我中学时基础没学好，想问一句什么是全排列？要不然可以没事的
时候想想。
--
点解啊，点解啊？
-- 捶胸蹬足状
※ 来源:．月光软件站 http://www.moon-soft.com．[FROM: 202.102.171.193]
发信人: ycs830 (老山羊), 信区: CLanguage
标 题: Re: 输出全排列，谁有更好的方法？
发信站: 网易虚拟社区 (Tue Nov 9 11:21:56 1999), 站内信件
【 在 supermario (Mario) 的大作中提到: 】
N个人排队，列出所有排法。
可以用递归，或循环，从1-N排起，从后边换起。
--
※ 来源:．月光软件站 http://www.moon-soft.com．[FROM: 202.96.78.130]
发信人: girlrong (阿蓉), 信区: CLanguage
标 题: Re: 输出全排列，谁有更好的方法？
发信站: 网易 BBS (Tue Nov 9 11:26:39 1999), 转信
【 在 ycs830 (老山羊) 的大作中提到: 】
: 【 在 girlrong (阿蓉) 的大作中提到: 】
: : 【 在 ycs830 (老山羊) 的大作中提到: 】
: : 用N进制的方法吧。设一个N个单元的数组，对第一个单元做加一操作，满N进
: : 一。每加一次一就判断一下各位数组单元有无重复，有则再转回去做加一操作，没
: : .......
:
: 不敢恭维！
为什么？我用basic都可以实现，基本可用。要不你来个更好的，我这个方法确实
数目大了不行。
--
※ 来源:．网易 BBS bbs.netease.com．[FROM: 202.103.243.7]
发信人: girlrong (阿蓉), 信区: CLanguage
标 题: Re: 输出全排列，谁有更好的方法？
发信站: 网易 BBS (Tue Nov 9 11:41:37 1999), 转信
【 在 supermario (Mario) 的大作中提到: 】
: 【 在 girlrong (阿蓉) 的大作中提到: 】
: : 【 在 ycs830 (老山羊) 的大作中提到: 】
: : 用N进制的方法吧。设一个N个单元的数组，对第一个单元做加一操作，满N进
: : 一。每加一次一就判断一下各位数组单元有无重复，有则再转回去做加一操作，没
: : .......
: 这种算法应该避免判断有无重复，要不然算法时间就会是直线上升，
: 我中学时基础没学好，想问一句什么是全排列？要不然可以没事的
: 时候想想。
判断有无重复可以这样呀：再开一个数组，数组下标代表位置。而前一个数组
的单元值代表参与排列的元素的编号。第二个数组单元里如果为1说明该位置被占用
了，为0说明没被占用。以第一个数组的单元值为索引去看第二个数组单元是否为0
就可以知道位置是否被占用了，免了用循环判断有无重复。
第二个数组也可以用c的位运算来代替。
我这个办法是很久以前用的了，不知老山羊是不是不满足其速度?:)其实速度还
可以呀。
--
※ 修改:．girlrong 于 Nov 9 11:45:33 修改本文．[FROM: 202.103.243.7]
※ 来源:．网易 BBS bbs.netease.com．[FROM: 202.103.243.7]
发信人: supermario (Mario), 信区: CLanguage
标 题: Re: 输出全排列，谁有更好的方法？
发信站: 网易虚拟社区 (Tue Nov 9 12:02:00 1999), 站内信件
【 在 ycs830 (老山羊) 的大作中提到: 】
: 【 在 supermario (Mario) 的大作中提到: 】
:
: N个人排队，列出所有排法。
: 可以用递归，或循环，从1-N排起，从后边换起。
: .......
看来得用递归，循环的控制比较麻烦，用后退的方法比较方便。
--
点解啊，点解啊？
-- 捶胸蹬足状
※ 来源:．月光软件站 http://www.moon-soft.com．[FROM: 202.102.171.193]
发信人: terran (terran), 信区: CLanguage
标 题: Re: 输出全排列，谁有更好的方法？
发信站: 网易虚拟社区 (Tue Nov 9 12:33:28 1999), 站内信件
【 在 supermario (Mario) 的大作中提到: 】
: 【 在 ycs830 (老山羊) 的大作中提到: 】
: : 【 在 supermario (Mario) 的大作中提到: 】
: :
: : N个人排队，列出所有排法。
: .......
用递归最方便!
但用循环并不是不行!只需要使用指针连接配合空间申请即可!
--
※ 来源:．月光软件站 http://www.moon-soft.com．[FROM: 210.75.56.43]
发信人: mrcloud (阿豪), 信区: CLanguage
标 题: Re: 输出全排列，谁有更好的方法？
发信站: 网易虚拟社区 (Tue Nov 9 13:27:52 1999), 站内信件
【 在 ycs830 (老山羊) 的大作中提到: 】
: 从1到N，输出全排列，共N！条。试试看！
用回溯啊？这是最好最正规的方法了。
--
阿豪 [email protected]
最好的BCB学习网站 C++Builder开发网络(http://a_hao.163.net)
C++Builder 论坛(http://cppbahao.abc.yesite.com)
※ 来源:．月光软件站 http://www.moon-soft.com．[FROM: 202.101.20.116]
发信人: supermario (Mario), 信区: CLanguage
标 题: Re: 输出全排列，谁有更好的方法？
发信站: 网易虚拟社区 (Tue Nov 9 17:12:56 1999), 站内信件
【 在 girlrong (阿蓉) 的大作中提到: 】
: 【 在 supermario (Mario) 的大作中提到: 】
: : 这种算法应该避免判断有无重复，要不然算法时间就会是直线上升，
: : 我中学时基础没学好，想问一句什么是全排列？要不然可以没事的
: : 时候想想。
: .......
今天上班糊涂了一天，只写了个开头，看看谁能？
#include <stdio.h>
#include <malloc.h>
main()
{
int i,j,index;
int *list,*out;
printf("please input index number\n");
scanf("%d",&index);
if((list = calloc(index,sizeof(int))) == NULL){
printf("calloc list fault!!!\n");
exit(0);
}
if((out = calloc(index,sizeof(int))) == NULL){
printf("calloc out fault!!!\n");
exit(0);
}
for(i = 0;i < index;i++){
*(list + i) = i;
printf("%d",list[i]);
}
//add your code to ......
printf("program end!!!\n");
return(0);
}
--
点解啊，点解啊？
-- 捶胸蹬足状
※ 来源:．月光软件站 http://www.moon-soft.com．[FROM: 202.102.171.193]
发信人: ycs830 (老山羊), 信区: CLanguage
标 题: 有关全排列的问题，再试试！
发信站: 网易虚拟社区 (Tue Nov 9 14:25:36 1999), 站内信件
N>=17，所以考虑速度，因为N**N远远大于N!。
有没有现成的方法，否则就用我今天晚上想出来的方法了。
我想先从1到N自然排列，然后开始交换，第i个交换i次后，就该进位了，
i以后的重新排列。大概其就是这个思路。
--
※ 来源:．月光软件站 http://www.moon-soft.com．[FROM: 202.96.79.14]
发信人: jackyrong (), 信区: CLanguage
标 题: Re: 有关全排列的问题，再试试！
发信站: 网易虚拟社区 (Tue Nov 9 16:26:20 1999), 站内信件
【 在 ycs830 (老山羊) 的大作中提到: 】
: N>=17，所以考虑速度，因为N**N远远大于N!。
:
: 有没有现成的方法，否则就用我今天晚上想出来的方法了。
:
: .......
用回溯最快，如：6！
#include <iostream.h>
const int n=6;
const int m=6;
int t;
int counter;
void out(const int a[m])
{
int i1;
for (i1=1;i1<=m;i1++)
cout<<a[i1]<<" ";
cout<<endl;
t=m;
counter=counter+1;
return;
}
int main()
{
counter=0;
const int m=3;
int i;
int a[m+1];
for (i=1;i<=m+1;i++)
a[i]=i;
out(a);
do {
if (a[t]==n-m+t) t=t-1;
else {
a[t]=a[t]+1;
if (t<m) for (i=t+1;i<=m;i++)
{a[i]=a[i-1]+1;}
out(a);
}
}
while (t!=0);
cout<<"The anwers are"<<counter<<endl;
return 0;
}
--
欢迎到最新 最全的学友成龙的网站：JACKYRONG.126.com
※ 来源:．月光软件站 http://www.moon-soft.com．[FROM: ]
发信人: girlrong (阿蓉), 信区: CLanguage
标 题: Re: 有关全排列的问题，再试试！
发信站: 网易虚拟社区 (Tue Nov 9 17:06:12 1999), 站内信件
【 在 ycs830 (老山羊) 的大作中提到: 】
: N>=17，所以考虑速度，因为N**N远远大于N!。
:
: 有没有现成的方法，否则就用我今天晚上想出来的方法了。
:
: .......
天，大于17。哪怕只有17，全排列数也高达355687428096000，三百万亿种。
假设一秒钟输出三百万种(应该够快了吧?)，全部输出也要一亿秒钟。老山羊啊，
不得了。
这是我的方法。只要先把数组声明好，填上初始值，然后反复调用AddOne()
和Result()，全排列就出来了。函数AddOne()实在无法有效地结构化了，只好用
了两个goto。
你的交换法应该比我的快。但我认为无论如何排列元素达17个以上是现在的
电脑所完成不了的。
#include <stdio.h>
#include <string.h>
typedef char MYTYPE;
void Result(MYTYPE * pPos,int n);
int AddOne(MYTYPE *pPos,MYTYPE *pPers,int n);
int main()
{
int n;//参与排列的人数
printf("请输入一个大于0的整数：");
scanf("%d",&n);
if(n<=0) return 1;
if(n>=10)
{
printf("最好别输这么大的数");
return 1;
}
//下标代表位置编号，单元值代表占据该位置的人员编号
MYTYPE *pPos=new MYTYPE[n*sizeof(MYTYPE)];
//下标代表人员编号，单元值代表该人员是否参与了排列
MYTYPE *pPers=new MYTYPE[n*sizeof(MYTYPE)];
//用来统计排列数的变量
int Total=0;
//先造出第一种排列
for(int i=0;i<n;i++)
{
pPos[i]=n-1-i;
pPers[i]=1;
}
Result(pPos,n);//第一种排列已经有了，输出。
Total++;
//下面输出剩下的各种排列
while(AddOne(pPos,pPers,n))
{
Result(pPos,n);
Total++;
}
printf("全排列数：%d\n\n\n",Total);
delete[] pPers;
delete[] pPos;
return 1;
}
////////////////////////////////////////////////
int AddOne(MYTYPE *pPos,MYTYPE *pPers,int n)
{
//返回值为1说明还可以有其他排列方案。返回值为0说明全排列已经全部处
理完毕。
//pPos[i]：编号为i的人员所占据的位置
//pPers[x]：编号为x的位置是否被人占据。0：空 1：被占据
int i=0;
aaa:
pPers[pPos[i]]=0;
bbb:
pPos[i]++;
if(pPos[i]>=n)
{
//需要进位
pPos[i]=-1;//该位置的人员未定
i++;
if(i<n) goto aaa;
return 0;
}
if(pPers[pPos[i]])
{
//被占用了
goto bbb;
}
//既不需进位，该人员也未被占用
pPers[pPos[i]]=1;
i--;
//处理那些未定人员的位置
for(;i>=0;i--)
{
if(pPos[i]<0)
{
do
{
pPos[i]++;
}
while(pPers[pPos[i]]);
pPers[pPos[i]]=1;
}
}
return 1;
}
void Result(MYTYPE * pPos,int n)
{
for(int i=0;i<n;i++)
{
printf("%5d",pPos[i]+1);
}
printf("\n\n");
}
--
※ 来源:．月光软件站 http://www.moon-soft.com．[FROM: 202.103.244.18]
发信人: zelor (张作乐), 信区: CLanguage
标 题: Re: 有关全排列的问题，再试试！
发信站: 网易虚拟社区 (Tue Nov 9 18:24:50 1999), 站内信件
回溯的程序看得人头好大……哪位帮我掰一掰？
【 在 jackyrong () 的大作中提到: 】
: 【 在 ycs830 (老山羊) 的大作中提到: 】
: : N>=17，所以考虑速度，因为N**N远远大于N!。
: :
: : 有没有现成的方法，否则就用我今天晚上想出来的方法了。
: .......
--
冬雷滚滚夏雨雪，
山无棱，天地合，
WINDOWS再没有BUG，
才敢与君绝！
———作乐的爱情格言
※ 来源:．月光软件站 http://www.moon-soft.com．[FROM: 202.103.47.202]
发信人: supermario (发烧啦), 信区: CLanguage
标 题: Re: 有关全排列的问题，再试试！
发信站: 网易虚拟社区 (Tue Nov 9 20:50:35 1999), 站内信件
【 在 jackyrong () 的大作中提到: 】
: 【 在 ycs830 (老山羊) 的大作中提到: 】
: : N>=17，所以考虑速度，因为N**N远远大于N!。
: :
: : 有没有现成的方法，否则就用我今天晚上想出来的方法了。
: .......
此算法有问题，不能得到正确结果，看在写了这么长的面子上
给20分。
--
点解啊，点解啊？
-- 捶胸蹬足状
※ 来源:．月光软件站 http://www.moon-soft.com．[FROM: 202.102.129.240]
发信人: zelor (张作乐), 信区: CLanguage
标 题: Re: 有关全排列的问题，再试试！
发信站: 网易虚拟社区 (Tue Nov 9 21:36:10 1999), 站内信件
您给一个正确的行不行？这两天看程序看得头都大了。
期中考试考不好怪你们。:P
【 在 supermario (发烧啦) 的大作中提到: 】
: 【 在 jackyrong () 的大作中提到: 】
: : 【 在 ycs830 (老山羊) 的大作中提到: 】
: : .......
: 此算法有问题，不能得到正确结果，看在写了这么长的面子上
: .......
--
冬雷滚滚夏雨雪，
山无棱，天地合，
WINDOWS再没有BUG，
才敢与君绝！
———作乐的爱情格言
※ 来源:．月光软件站 http://www.moon-soft.com．[FROM: 202.103.47.202]
发信人: ycs830 (老山羊), 信区: CLanguage
标 题: 关于全排列问题，谢谢大家参与，请继续。
发信站: 网易虚拟社区 (Wed Nov 10 09:09:43 1999), 站内信件
我是算术系毕业的，不知学计算机的仁兄们学没学过这个问题的标准
算法，按理说这是一个常用的算法，而且也锻炼能力，书上应该有。思路
我倒是有，实现也不困难，但是想速度快点。
只要遍历就行，不必考虑顺序，也不必考虑输出后文件太大，因为我
只是想在其中筛选。而且不必非得到17，咱只是讨论算法。
程序请用标准c写，N的值由用户输入，用动态数组，我可以在小型机
上玩。
不写程序写出思路也行，大家可以共同探讨，找出更好的方法。仁者
见仁，智者见智。既然在c区讨论，找出好方法就行。
--
※ 来源:．月光软件站 http://www.moon-soft.com．[FROM: 202.96.79.14]
发信人: mrcloud (阿豪), 信区: CLanguage
标 题: Re: 关于全排列问题，谢谢大家参与，请继续。
发信站: 网易虚拟社区 (Wed Nov 10 09:37:07 1999), 站内信件
【 在 ycs830 (老山羊) 的大作中提到: 】
: 我是算术系毕业的，不知学计算机的仁兄们学没学过这个问题的标准
: 算法，按理说这是一个常用的算法，而且也锻炼能力，书上应该有。思路
: 我倒是有，实现也不困难，但是想速度快点。
: 只要遍历就行，不必考虑顺序，也不必考虑输出后文件太大，因为我
: .......
还有一个办法，不过链表插入可能导致速度太慢。
要得到n的全排列,只要在n-1全排列的基础上,一个隔一个插入n即可，
所以可以用递归极方便地实现,但我找不到好的插入算法。
--
阿豪 [email protected]
最好的BCB学习网站 C++Builder开发网络(http://iamahao.yeah.net)
C++Builder 论坛(http://cppbahao.abc.yesite.com)
※ 来源:．月光软件站 http://www.moon-soft.com．[FROM: 202.101.16.129]
发信人: ycs830 (老山羊), 信区: CLanguage
标 题: Re: 关于全排列问题，谢谢大家参与，请继续。
发信站: 网易虚拟社区 (Wed Nov 10 09:46:13 1999), 站内信件
【 在 mrcloud (阿豪) 的大作中提到: 】
内存得大得惊人，否则无法记忆N-1次的全排列。用磁盘倒？慢！
--
※ 来源:．月光软件站 http://www.moon-soft.com．[FROM: 202.96.79.14]
发信人: girlrong (阿蓉), 信区: CLanguage
标 题: Re: 关于全排列问题，谢谢大家参与，请继续。
发信站: 网易虚拟社区 (Wed Nov 10 10:16:11 1999), 站内信件
【 在 ycs830 (老山羊) 的大作中提到: 】
: 【 在 mrcloud (阿豪) 的大作中提到: 】
: 内存得大得惊人，否则无法记忆N-1次的全排列。用磁盘倒？慢！
n个元素全排列，每得到(n-1)个元素的全排列，就把第n个元素和那n-1个元
素依次交换，每交换一次就是一个n个元素的全排列。交换可以象冒泡法排序那样
相邻两个元素进行交换，这样就免了阿豪的方法中的链表的插入操作。例如：
4 3 2 1
假设 3 2 1 已经是n-1个元素的全排列，那么第n个元素4可以这样交换
：
3 4 2 1
3 2 4 1
3 2 1 4
每交换一次就是个新的n个元素的全排列。等我想想看如何实现。
也没必要把每次的全排列都记在内存里，用过就可以丢了嘛。
--
※ 来源:．月光软件站 http://www.moon-soft.com．[FROM: 202.103.243.166]
发信人: mrcloud (阿豪), 信区: CLanguage
标 题: Re: 关于全排列问题，谢谢大家参与，请继续。
发信站: 网易虚拟社区 (Wed Nov 10 11:06:12 1999), 站内信件
【 在 ycs830 (老山羊) 的大作中提到: 】
: 【 在 mrcloud (阿豪) 的大作中提到: 】
: 内存得大得惊人，否则无法记忆N-1次的全排列。用磁盘倒？慢！
不需要啊？
我是说用递归,在最下一层输出。无须记忆n-1的全排列。
--
阿豪 [email protected]
最好的BCB学习网站 C++Builder开发网络(http://iamahao.yeah.net)
C++Builder 论坛(http://cppbahao.abc.yesite.com)
※ 来源:．月光软件站 http://www.moon-soft.com．[FROM: 202.101.16.129]
发信人: mrcloud (阿豪), 信区: CLanguage
标 题: Re: 关于全排列问题，谢谢大家参与，请继续。
发信站: 网易虚拟社区 (Wed Nov 10 11:09:26 1999), 站内信件
【 在 girlrong (阿蓉) 的大作中提到: 】
: 【 在 ycs830 (老山羊) 的大作中提到: 】
: : 【 在 mrcloud (阿豪) 的大作中提到: 】
: : 内存得大得惊人，否则无法记忆N-1次的全排列。用磁盘倒？慢！
:
: .......
不错！
--
阿豪 [email protected]
最好的BCB学习网站 C++Builder开发网络(http://iamahao.yeah.net)
C++Builder 论坛(http://cppbahao.abc.yesite.com)
※ 来源:．月光软件站 http://www.moon-soft.com．[FROM: 202.101.16.129]
发信人: ycs830 (老山羊), 信区: CLanguage
标 题: Re: 关于全排列问题，谢谢大家参与，请继续。
发信站: 网易虚拟社区 (Wed Nov 10 11:55:53 1999), 站内信件
【 在 girlrong (阿蓉) 的大作中提到: 】
嘿嘿，1到3的排列方法共有3！种，以此类推。
--
※ 来源:．月光软件站 http://www.moon-soft.com．[FROM: 202.96.78.129]
发信人: terran (terran), 信区: CLanguage
标 题: Re: 关于全排列问题，谢谢大家参与，请继续。
发信站: 网易虚拟社区 (Wed Nov 10 14:51:15 1999), 站内信件
【 在 girlrong (阿蓉) 的大作中提到: 】
: 【 在 ycs830 (老山羊) 的大作中提到: 】
: : 【 在 mrcloud (阿豪) 的大作中提到: 】
: : 内存得大得惊人，否则无法记忆N-1次的全排列。用磁盘倒？慢！
:
: .......
girlrong 你如果不用递归,不用动态指针的话,N的数值回受到限制的.不好!
解决方法可以是:
在一个function x中用for,并把for中的极大限制指传递归给function x
,然后在配合指针空间的申请!就ok了!
--
※ 来源:．月光软件站 http://www.moon-soft.com．[FROM: 210.75.56.43]
发信人: girlrong (阿蓉), 信区: CLanguage
标 题: Re: 关于全排列问题，谢谢大家参与，请继续。
发信站: 网易虚拟社区 (Wed Nov 10 22:15:23 1999), 站内信件
【 在 terran (terran) 的大作中提到: 】
: 【 在 girlrong (阿蓉) 的大作中提到: 】
: : 【 在 ycs830 (老山羊) 的大作中提到: 】
: :
: : .......
: .......
我前面给了个例子，没有用递归。算到8都还可以。今天想了一下递归，发现用递
归需控制的东西还更多。你有什么好主意没有？
--
※ 来源:．月光软件站 http://www.moon-soft.com．[FROM: 202.103.243.1]
发信人: ycs830 (老山羊), 信区: CLanguage
标 题: 关于全排列，这样行不行
发信站: 网易虚拟社区 (Wed Nov 10 17:24:19 1999), 站内信件
我大概其试了一下，这样行不行？明天再改进。循环次数应该正好。
语句写得不好，调了半天。
# include <stdio.h>
# define N 7
main()
{
int i,j,k,m,n,l[N],a[N];
/* 赋初值 */
for(i=0;i<N;i++)
{
a[i]=0;l[i]=i; /* a[i]-1是第i个元素交换的次数 */
}
k=1;m=2;put(l);
while(1)
{
n=l[1];l[1]=l[0];l[0]=n;put(l); /* 头两个先换一下 */
/* 判断该换哪个了 */
while(a[m-2] == m)
m++;
if(m==N) break;
/* 下面是整理过程，可能还有办法 */
j=0;n=m/2;
for(i=0,j=m-1;i<n;i++,j--)
{
k=l[i];
l[i]=l[j];
l[j]=k;
} /* 以上是从小到大重排，下面处理好了可能不必做，因为可以无序
*/
a[m-2]++;
/* 下面该把第j个和第m个交换 */
j=m-a[m-2];
n=l[j];l[j]=l[m];l[m]=n;
put(l);
/* m以前的重排 */
for(i=0;i<m-2;i++)
a[i]=0;
m=2;
}
}
put(int *l)
{
int i;
for(i=0;i<N;i++)
printf("%d",l[i]);
putchar('\n');
}
--
※ 来源:．月光软件站 http://www.moon-soft.com．[FROM: 202.96.78.129]
发信人: jackyrong (), 信区: CLanguage
标 题: Re: 关于全排列，这样行不行
发信站: 网易虚拟社区 (Wed Nov 10 18:28:09 1999), 站内信件
【 在 ycs830 (老山羊) 的大作中提到: 】
: 我大概其试了一下，这样行不行？明天再改进。循环次数应该正好。
: 语句写得不好，调了半天。
: # include <stdio.h>
: # define N 7
: .......
思想：用A：ARRAY[1。。N] OF INTEGER 放元素
初始化：
for i:=1 to n do a[i]:=i;
输出 A1，A2，。。。AN；
FOR I：=2 TO N ！ DO
BEGIN
求出A1，A2，。。。。。AN的下一个排列；
输出A1，A2，A3，。。。AN；
以N=4为例，
在1234每个数字上加上箭头，〈- 〈-〈-〈-
1 2 3 4，当箭头所指一侧的数比该数小时，
称为该数的活动壮态，即1234中，2，3，4该处于活动壮态
1） 输出A1，A2，。。。AN作为一种生成的排列，若拍列中已没有处于活动
壮态的元素，生成过程结束，否则转第二步
2） 求处于活动壮态的最大值，设为M，并将其和箭头一侧的元素交换（包括
箭头）；
3） 比M大的所有元素的箭头改向，转第1）。
对1234，则
1234 〈-〈-〈-〈-
1 2 3 4
1243 〈-〈-〈-〈-
1243
1423 〈-〈-〈-〈-
1423
4123 〈-〈-〈-〈-
4 1 2 3
4132 -〉〈-〈-〈-
4 1 3 2
1432 〈- -〉〈-〈-
1 4 3 2
1342 〈-〈- -〉 〈-
1 3 4 2
。。。。。。
2134 〈-〈- -〉 -〉
2 1 3 4
--
欢迎到最新 最全的学友成龙的网站：JACKYRONG.126.com
※ 来源:．月光软件站 http://www.moon-soft.com．[FROM: ]
发信人: zelor (张作乐), 信区: CLanguage
标 题: Re: 关于全排列，这样行不行
发信站: 网易虚拟社区 (Wed Nov 10 19:46:49 1999), 站内信件
列一个数组arr[n];
用一个指向该叔祖的指针p;
for (i=1;i<=n;i++)
对p进行模i的加法，不断通过p打印值……；
这样行不行得通？好象还有很多细节没有注意到？
临时所写，瞎灌一篇。
【 在 jackyrong () 的大作中提到: 】
: 【 在 ycs830 (老山羊) 的大作中提到: 】
: : 我大概其试了一下，这样行不行？明天再改进。循环次数应该正好。
: : 语句写得不好，调了半天。
: : # include <stdio.h>
: .......
--
你说我是新手，那么你错了。
你说我是高手，那么我错了。
——篡改自某部反映青少年题材的电视剧
※ 来源:．月光软件站 http://www.moon-soft.com．[FROM: 202.103.45.170]
发信人: supermario (发烧啦), 信区: CLanguage
标 题: Re: 关于全排列，这样行不行
发信站: 网易虚拟社区 (Wed Nov 10 21:21:20 1999), 站内信件
【 在 ycs830 (老山羊) 的大作中提到: 】
: 我大概其试了一下，这样行不行？明天再改进。循环次数应该正好。
: 语句写得不好，调了半天。
: # include <stdio.h>
: # define N 7
: .......
速度不错，当N = 8时在PII400上只要两分钟，比阿蓉的快一些，
但是两台机器不太一样，回去再比较一下。
--
点解啊，点解啊？
-- 捶胸蹬足状
※ 来源:．月光软件站 http://www.moon-soft.com．[FROM: 202.102.129.253]
发信人: girlrong (阿蓉), 信区: CLanguage
标 题: Re: 关于全排列，这样行不行
发信站: 网易虚拟社区 (Wed Nov 10 22:49:48 1999), 站内信件
【 在 ycs830 (老山羊) 的大作中提到: 】
: 我大概其试了一下，这样行不行？明天再改进。循环次数应该正好。
: 语句写得不好，调了半天。
: # include <stdio.h>
: # define N 7
: .......
试了一下，用递归要控制太多东西。我这里有个递归的框架，正好处理次数
也是n！。但不知道交换和输出的代码该加在哪里，高手们有兴趣试试看。
老山羊真出了个难题。
#include <stdio.h>
#include <string.h>
typedef char MYTYPE;
int total=0;
int Permute(MYTYPE *pPos,int i,int n);
int main()
{
int n;//参与排列的人数
printf("请输入一个大于0的整数：");
scanf("%d",&n);
if(n<=0) return 1;
MYTYPE *pPos=new MYTYPE[n];
//用来统计排列数的变量
int Total=0;
Permute(pPos,1,n);
printf("\n\n全排列数：%d\n\n",total);
delete[] pPos;
return 1;
}
int Permute(MYTYPE *pPos,int i,int n)
{
int k,m=n-1;
for(k=i;k>=0;k--)
{
if(i==m)
{
//也许交换和输出的代码应该写在这里
total++;
}
if(i<m) Permute(pPos,i+1,n);
}
return 1;
}
--
※ 来源:．月光软件站 http://www.moon-soft.com．[FROM: 202.103.243.1]
发信人: mrcloud (阿豪), 信区: CLanguage
标 题: Re: 关于全排列，这样行不行
发信站: 网易虚拟社区 (Thu Nov 11 00:05:43 1999), 站内信件
【 在 ycs830 (老山羊) 的大作中提到: 】
: 我大概其试了一下，这样行不行？明天再改进。循环次数应该正好。
: 语句写得不好，调了半天。
: # include <stdio.h>
: # define N 7
: .......
还是用递归吧,在我的k6-233上,N=8只用不到10秒。
优化一下可以更快。
const int MAX=8;
int number[MAX];
void InsertNum(int n);
void OutPut();
unsigned int count=0;
//--------------------------------------------------------------------
-------
void __fastcall TForm1::Button1Click(TObject *Sender)
{
InsertNum(1);
Edit1->Text=IntToStr(count);
}
//--------------------------------------------------------------------
-------
void InsertNum(int n)
{
bool End=false;
if(n==MAX)
End=true;
number[n-1]=n;
int temp;
for(int i=0;i<n;i++)
{
if(i)
{
temp=number[n-i];
number[n-i]=number[n-i-1];
number[n-i-1]=temp;
}
if(End)
OutPut();
else
{
InsertNum(n+1);
for(int j=0;j<n;j++)
number[j]=number[j+1];
}
}
}
void OutPut()
{
AnsiString Result="";
for(int i=0;i<MAX;i++)
Result+=number[i];
Form1->RichEdit1->Lines->Strings[count++]=Result;
}
--
阿豪 [email protected]
最好的BCB学习网站 C++Builder开发网络(http://iamahao.yeah.net)
C++Builder 论坛(http://cppbahao.abc.yesite.com)
※ 来源:．月光软件站 http://www.moon-soft.com．[FROM: 202.96.243.143]
发信人: mrcloud (阿豪), 信区: CLanguage
标 题: Re: 关于全排列，这样行不行
发信站: 网易虚拟社区 (Thu Nov 11 00:17:09 1999), 站内信件
【 在 mrcloud (阿豪) 的大作中提到: 】
Sorry,差点忘记说了,谢谢girlrong给我灵感,用交换代替插入操作。
--
阿豪 [email protected]
最好的BCB学习网站 C++Builder开发网络(http://iamahao.yeah.net)
C++Builder 论坛(http://cppbahao.abc.yesite.com)
※ 来源:．月光软件站 http://www.moon-soft.com．[FROM: 202.96.243.143]
发信人: ycs830 (老山羊), 信区: CLanguage
标 题: 有关全排列，我改动一下，变成这样
发信站: 网易虚拟社区 (Thu Nov 11 10:01:02 1999), 站内信件
这两天我抛出一块砖头，引来这么多美玉，真是受惠非浅。我把程
序改动了一下，变成这样啦，智力和精力所限，我也改不动了。各位的
程序我好好读一读，开拓一下自己的思路。
下面我们是否讨论一下组合了？但组合好像较简单，从M个球里取N
个，列出所有组合，不用排列了，所以从大到小即可。可重复取样的也
很简单，比如从扑克牌中取出4张算24，哪天我试试看。
# include <stdio.h>
# include <alloc.h>
int N;
main()
{
int i,j,k,m,n,*l,*a,m2;
scanf("%d",&N);
if(N<3)
{
puts("N太小!");
exit(1);
}
/* 开数组 */
l=malloc(N*sizeof(int));
a=malloc(N*sizeof(int));
/* 赋初值 */
for(i=0;i<N;i++)
{
a[i]=0;l[i]=i+1; /* a[i]-1是第i个元素交换的次数 */
}
m=2;put(l);
do
{
n=l[1];l[1]=l[0];l[0]=n;put(l); /* 头两个先换一下 */
/* 判断该换哪个了 */
while(a[m-2] == m)
m++;
if(m==N) break;
/* 下面是整理过程，可能还有办法 */
n=m>>1;
for(i=0,j=m-1;i<n;i++,j--)
{
k=l[i];
l[i]=l[j];
l[j]=k;
} /* 以上是从小到大重排，下面处理好了可能不必做，因为可以无序
*/
m2=m-2;
a[m2]++;
/* 下面该把第j个和第m个交换 */
j=m-a[m2];
n=l[j];l[j]=l[m];l[m]=n;
put(l);
/* m以前的重排 */
for(i=0;i<m2;i++)
a[i]=0;
m=2;
} while(1);
}
put(int *l)
{
int i;
for(i=0;i<N;i++)
printf(" %2d",l[i]);
putchar('\n');
}
--
※ 来源:．月光软件站 http://www.moon-soft.com．[FROM: 202.96.78.129]
发信人: grsm (grsm), 信区: CLanguage
标 题: 我也写一个全排列的程序
发信站: 网易虚拟社区 (Thu Nov 11 16:55:14 1999), 站内信件
看了老山羊的题目，觉得很有意思，也写了一段程序。
#include <stdio.h>
#define n 5
int a[n],b[n];
void swap(int m)
{
int b1=b[m];
int b0=b1;
while(a[b0]>=m){
b0--;
if(b0<0)b0=n-1;
}
int temp=a[b0];
a[b0]=a[b1];
a[b1]=temp;
int a0=a[b0];
int a1=a[b1];
temp=b[a0];
b[a0]=b[a1];
b[a1]=temp;
}
void output()
{
for(int j=0;j<n;j++){
printf("%d ",a[j]);
}
printf("\n");
}
void permute(int m)
{
m--;
for(int i=m;i>=0;i--){
permute(m);
if(i>0){
swap(m);
output();
}
}
}
void main()
{
for(int i=0;i<n;i++){
a[i]=b[i]=i;
}
output();
permute(n);
}
--
※ 来源:．月光软件站 http://www.moon-soft.com．[FROM: 202.102.240.99]
发信人: girlrong (阿蓉), 信区: CLanguage
标 题: 全排列问题答案大比武
发信站: 网易虚拟社区 (Thu Nov 11 22:05:02 1999), 站内信件
不少人都做了老山羊的全排列问题，共有五人给出了六个程序。看了一下，
jackyrong的程序有问题，没有输出全排列，而是输出了顺次加一的自然数。ter
ran的程序也得不出结果，并且还有些语法错误。你们两位的算法可能没问题，只
是没有经过调式。阿豪的程序最怪，初次编译，竟有错误无数。再一看，原来是
用bcb写的。只好先化为vc6.0下的console程序（向阿豪保证，绝对没有伤及算法
部分）。还有个奇怪的地方。老山羊的put函数居然没有原型，难道在老山羊的编
译器上函数可以没有原型？当然，这也不是问题，在我这里加上就好了。
先看准确性。以4个元素全排列，将结果重定向到文件里查看，大家的结果都
很完整。
再看速度。 在我的P200MMX，64M内存机器上，删除所有程序中的输出语句，
然后算10个元素的全排列，四个程序所花时间如下：
老山羊的第一个程序：5秒
老山羊的第二个程序：5秒
阿豪的程序：6秒
grsm的程序：10秒
斑竹我的程序：16秒
呜呼，为什么我的程序这么慢？看来得把大家的程序好好学学。
全排列问题很有用。在解决某些问题时需要穷举各种可能的情况，这时全排
列问题就可派上用场了。正好精华区里开了个算法集锦的栏目，这是个很好的例
子，稍后把各个程序都放进去，大家可以参考。
--
※ 来源:．月光软件站 http://www.moon-soft.com．[FROM: 202.103.244.34]
发信人: supermario (夜游九州), 信区: CLanguage
标 题: 算法主要考虑的因素
发信站: 网易虚拟社区 (Fri Nov 12 01:09:35 1999), 站内信件
看了大家的全排列算法，想指出一点，算法的主要目的是减少
程序执行时间，首先要考虑的是减少循环次数，象用筛法从
n*n个递增数组里去掉有相同值的方法是不可取的，然后就是
控制循环的嵌套层数，尽可能的将多重循环变为更少层数的循
环，然后就是函数调用，要知道当一个算法执行的次数越多，
由于函数调用带来的附加机器指令就不可忽视，阿蓉的程序就
有这个问题，由于采用了外部函数的调用，每次入栈出栈就增
加了不少的附加指令，所以在写这样的程序时要尽量减少函数
调用，最好所有的循环操作在一个函数里完成。这也是程序结
构化与执行效率的矛盾，我以前为了赶工写的很多程序，结果
在后期整理时为了增强程序的可读性，将很多为了不想调用来
调用去而全部写在一个主函数的功能代码做成函数形式移出
main()，结果发现程序的执行效率大大降低。这是很好笑的
一件事。
另外就是算法对内存的要求，这个我倒是一般不注意，我用的
机器上一般都有2G以上的内存，但是在PC平台上，这也是应该
注意的。
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
人生五十年，去事恍如梦幻；下天之内，岂有长生不死者
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
人生得意需尽欢，莫使金樽空对月
---------------------------------------------------
我的心早已经一片黑暗，再没有什么是可以点燃。
---------------------------------------------------
--
点解啊，点解啊？
-- 捶胸蹬足状
※ 修改:．supermario 于 Nov 12 03:18:39 修改本文．[FROM: 202.102.171.158]
※ 来源:．月光软件站 http://www.moon-soft.com．[FROM: bbs.szptt.net.c]
发信人: mrcloud (阿豪), 信区: CLanguage
标 题: Re: 全排列问题答案大比武
发信站: 网易虚拟社区 (Fri Nov 12 11:58:50 1999), 站内信件
【 在 supermario (发烧啦) 的大作中提到: 】
: 【 在 mrcloud (阿豪) 的大作中提到: 】
: : 【 在 supermario (发烧啦) 的大作中提到: 】
: : .......
: 阿豪啊，你的程序好像有问题，我运行了4分多钟还没结果，
: .......
我又编译了一次去掉了一句话：“//--------”
把return的返回值加上了。
用的是VC5的console程序。
0 error 0 warning
在我的k6-233上算12用了1分30秒。麻烦你再试试。:)
#include <stdio.h>
const int MAX=12;
char number[MAX+1];
void InsertNum(int n);
void OutPut();
int main()
{
number[MAX]='\0';
InsertNum(1);
puts("OK");
return 0;
}
void InsertNum(int n)
{
bool End=false;
if(n==MAX)
End=true;
//number[n-1]=n+48;为写入文件方便,所以加了48
number[n-1]=n;
char temp;
for(int i=0;i<n;i++)
{
if(i)
{
temp=number[n-i];
number[n-i]=number[n-i-1];
number[n-i-1]=temp;
}
if(End)
OutPut();
else
{
InsertNum(n+1);
for(int j=0;j<n;j++)
number[j]=number[j+1];
}
}
}
void OutPut()
{
}
--
阿豪 [email protected]
最好的BCB学习网站 C++Builder开发网络(http://iamahao.yeah.net)
C++Builder 论坛(http://cppbahao.abc.yesite.com)
※ 修改:．mrcloud 于 Nov 12 12:03:42 修改本文．[FROM: 202.101.48.152]
※ 来源:．月光软件站 http://www.moon-soft.com．[FROM: 202.101.48.152]
发信人: terran (terran), 信区: CLanguage
标 题: 斑竹,我的全排列来了!SURE WIN!
发信站: 网易虚拟社区 (Fri Nov 12 09:16:29 1999), 站内信件
抱歉,我用了自己的头文件,麻烦改一改.程序在我的机上通过了!
这次程序的算法和上次那个基本一样,只不过为了加快速度我用了数组!
另外,比较的时候,希望斑竹规定要用同样的I/O语句,因为程序里对速度影响
最大的除了算法,就是I/O语句了!
#include "myhead.h"
#define Max 8
int record[Max];
int repeat(int i);
main()
{
int j;
for(j=0;j<=Max;j++) record[j]=0;
for(j=1;j<=Max;j++)
{
record[1]=j;
repeat(1);
}
return ;
}
int repeat(int i)
{
int j,k,x,flag=1;
for(j=1;j<=Max;j++)
{
for(k=1;k<=i;k++)
{
if (record[k]==j)
{
flag=0;
break;
}
}
if(flag)
{
record[k]=j;
i++;
if(i<Max) repeat(i);
else
{
for(x=1;x<=Max;x++) printf("%d ",record[x]);
printf("\n");
}
if (j==Max) return 1;
record[k]=0;
i--;
}
flag=1;
}
}
--
※ 来源:．月光软件站 http://www.moon-soft.com．[FROM: 210.75.56.43]
发信人: girlrong (阿蓉), 信区: CLanguage
标 题: 全排列结果补充
发信站: 网易虚拟社区 (Sat Nov 13 16:02:00 1999), 站内信件
阿豪的新程序果然厉害，在我的P200MMX机器上去掉输出语句，用vc++6.0编
译成console程序，算11个元素全排列只花了56秒！不过老山羊的也只花56秒。你
们俩打个平手。至于terran的程序，非常遗憾，去掉输出语句后，10个元素全排
列也花了31秒，11个元素的全排列我没敢试，怎么也得几分钟吧。可能你的算法
还有待改进。jackyrong的不是c写的程序，我就没法试了。
这些结果只是我在我的机器上实验的结果，因水平有限，难免有不对的地方
，仅供参考而已。
--
※ 来源:．月光软件站 http://www.moon-soft.com．[FROM: 202.103.243.60]
|
|