数学建模社区-数学中国

标题: 输出一组数字的所有排列 [打印本页]

作者: kampoo 时间: 2005-12-29 14:29
标题: 输出一组数字的所有排列
输出一组数字的所有排列，最简单的算法是什么？

作者: fewrains 时间: 2006-1-1 13:15
<

>递归,从VChelp的算法版主那里抄来的:
<

> #define N_permutation 5 // 排列元素数量
<

>unsigned char flag[N_permutation]; // 标记元素是否被使用 unsigned char dat[N_permutation]; // 记录临时元素队列 unsigned char p_dat=0; // 对列指针
<

>void out_dat() // 输出对列dat中的内容 { for(int i=0;i<N_permutation;i++) cout<<dat<<' '; cout<<endl; }
4 M, M- V2 g2 V: b<>void permutation() // 再入函数，生成N_permutation个字母的所有排列, { // 最大递归次数为N_permutation unsigned char i; // 被再入函数入栈保护的局部变量 for(i=0;i<N_permutation;i++) { if (flag==0) { flag=1; // 标记元素被使用 dat[p_dat]=0x41+i; // 将字母添加到队列 p_dat++; - P8 e9 \5 w& c6 D4 {4 Z. O/ Q
<> if (p_dat==N_permutation) // 对列满输出， out_dat(); else permutation(); // 否则继续添加 p_dat--; flag=0; } } } void main() { permutation(); getch(); }[em07][em07][em07]
作者: fewrains 时间: 2006-1-1 13:16
<>前头要加上:$ W1 F, a& y7 {0 \. b& q7 |
<>#include <iostream> #include <conio.h> using namespace std; 
作者: fewrains 时间: 2006-1-3 00:44
<>非递归实现，效率不错
3 m9 Q! U1 V4 r [' e2 _<>#include <iostream> #include <conio.h> #include <windows.h> using namespace std;: d: G) c- s1 J0 [! x( ^5 `
<>void output(int *p); //输出函数 void permutation(int *p);//全排列函数
. \+ \: ^/ {1 L' A: P$ ?<>int a[]={1,2,3,4,5,6,7,8,9,10,11};//待排列数组 int N=sizeof(a)/sizeof(int); //数组长度 int *p=a; //数组指针
1 K( K7 I1 F; U6 |' r. n<>void main() { permutation(p); //调用全排列函数 output(p); //输出排列结果 getch(); }, u" m) B6 E- I4 H0 a. R
<>void permutation(int *p) { bool flag=false; //标志排列是否结束 int temp; //临时变量,用来交换数组元素
# }0 U! B G' f7 S2 {6 m<> while(1) { for(int i=0;i<N-1;i++) { flag=true; //如已排列完,falg为真. ]8 v, @4 G2 _7 @6 I
<> if(p<p[i+1]) //如果发现第一个倒序的数组元素,p[i+1]被称为倒序元素 { flag=false; //说明未排列完. O1 g( V1 W' `0 @& K/ ~: s- H
<> int j=0; while(p[j++]>=p[i+1]); //找到第一个大于或等于倒序元素的数组元素 j-=1; + |$ w9 F4 A+ |8 f3 S
<> temp=p[i+1]; //交换这两个元素 p[i+1]=p[j]; p[j]=temp;
+ B. W+ G A& m% Z<> j=0; while(j<(i+1)/2) //倒置倒充元素原位置以前的所有元素 { temp=p[j]; p[j]=p[i-j]; p[i-j]=temp; j++; } break; //跳出for循环, } } if(flag) //如果排列完,结束循环 break; //output(p); //输出排列结果 } }
7 L# I; ~+ I8 [2 P: ]6 T }4 i# D<>void output(int *p) { cout<<endl; for(int i=0;i<N;i++) cout<<p<<' ';' q9 p+ r- V5 i4 f) Z& L% w. j
<>} 
作者: dsg333 时间: 2006-2-19 05:16
还有吗？
作者: zhouming09 时间: 2006-3-6 17:01
太高深了不东
作者: zansan 时间: 2006-5-7 19:49
 递归容易明白,就是慢,这个算法就是好.找到"倒置位"后进行倒置.
作者: jinfly4997 时间: 2006-8-11 20:22
matlab里面好像有这个函数，我用过，但现在实在是既不起来了，你可以寻求帮助,但如果英语不太好，建议买一本参考教材看看相关命令，或者上网查一些有关命令的资料下载就是了，我的大部分matlab知识就是寻求网上帮助获得的，你也可以试试！
作者: sjian2001 时间: 2006-10-21 22:16
看过一篇文章是这么说的： 比如说求1，2，3的全排列， 先是{ 1 } 然后用2，在元素里所有空当插入 变成了{ 21 , 12} 然后用3，在元素里所有空当插入 {321,231,213,312,132,123} 算法还是好实现的。 不知道跟其他算法有什么效率差别。 

欢迎光临数学建模社区-数学中国 (http://www.madio.net/) Powered by Discuz! X2.5